diff options
Diffstat (limited to 'js/src/devtools/rootAnalysis')
42 files changed, 8341 insertions, 0 deletions
diff --git a/js/src/devtools/rootAnalysis/CFG.js b/js/src/devtools/rootAnalysis/CFG.js new file mode 100644 index 0000000000..1c83628411 --- /dev/null +++ b/js/src/devtools/rootAnalysis/CFG.js @@ -0,0 +1,179 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +// Utility code for traversing the JSON data structures produced by sixgill. + +"use strict"; + +// Find all points (positions within the code) of the body given by the list of +// bodies and the blockId to match (which will specify an outer function or a +// loop within it), recursing into loops if needed. +function findAllPoints(bodies, blockId, limits) +{ + var points = []; + var body; + + for (var xbody of bodies) { + if (sameBlockId(xbody.BlockId, blockId)) { + assert(!body); + body = xbody; + } + } + assert(body); + + if (!("PEdge" in body)) + return; + for (var edge of body.PEdge) { + points.push([body, edge.Index[0], limits]); + if (edge.Kind == "Loop") + points.push(...findAllPoints(bodies, edge.BlockId, limits)); + } + + return points; +} + +// Given the CFG for the constructor call of some RAII, return whether the +// given edge is the matching destructor call. +function isMatchingDestructor(constructor, edge) +{ + if (edge.Kind != "Call") + return false; + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + return false; + var variable = callee.Variable; + assert(variable.Kind == "Func"); + if (variable.Name[1].charAt(0) != '~') + return false; + + // Note that in some situations, a regular function can begin with '~', so + // we don't necessarily have a destructor in hand. This is probably a + // sixgill artifact, but in js::wasm::ModuleGenerator::~ModuleGenerator, a + // templatized static inline EraseIf is invoked, and it gets named ~EraseIf + // for some reason. + if (!("PEdgeCallInstance" in edge)) + return false; + + var constructExp = constructor.PEdgeCallInstance.Exp; + assert(constructExp.Kind == "Var"); + + var destructExp = edge.PEdgeCallInstance.Exp; + if (destructExp.Kind != "Var") + return false; + + return sameVariable(constructExp.Variable, destructExp.Variable); +} + +// Return all calls within the RAII scope of any constructor matched by +// isConstructor(). (Note that this would be insufficient if you needed to +// treat each instance separately, such as when different regions of a function +// body were guarded by these constructors and you needed to do something +// different with each.) +function allRAIIGuardedCallPoints(typeInfo, bodies, body, isConstructor) +{ + if (!("PEdge" in body)) + return []; + + var points = []; + + for (var edge of body.PEdge) { + if (edge.Kind != "Call") + continue; + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + continue; + var variable = callee.Variable; + assert(variable.Kind == "Func"); + const limits = isConstructor(typeInfo, edge.Type, variable.Name); + if (!limits) + continue; + if (!("PEdgeCallInstance" in edge)) + continue; + if (edge.PEdgeCallInstance.Exp.Kind != "Var") + continue; + + points.push(...pointsInRAIIScope(bodies, body, edge, limits)); + } + + return points; +} + +// Test whether the given edge is the constructor corresponding to the given +// destructor edge. +function isMatchingConstructor(destructor, edge) +{ + if (edge.Kind != "Call") + return false; + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + return false; + var variable = callee.Variable; + if (variable.Kind != "Func") + return false; + var name = readable(variable.Name[0]); + var destructorName = readable(destructor.Exp[0].Variable.Name[0]); + var match = destructorName.match(/^(.*?::)~(\w+)\(/); + if (!match) { + printErr("Unhandled destructor syntax: " + destructorName); + return false; + } + var constructorSubstring = match[1] + match[2]; + if (name.indexOf(constructorSubstring) == -1) + return false; + + var destructExp = destructor.PEdgeCallInstance.Exp; + if (destructExp.Kind != "Var") + return false; + + var constructExp = edge.PEdgeCallInstance.Exp; + if (constructExp.Kind != "Var") + return false; + + return sameVariable(constructExp.Variable, destructExp.Variable); +} + +function findMatchingConstructor(destructorEdge, body, warnIfNotFound=true) +{ + var worklist = [destructorEdge]; + var predecessors = getPredecessors(body); + while(worklist.length > 0) { + var edge = worklist.pop(); + if (isMatchingConstructor(destructorEdge, edge)) + return edge; + if (edge.Index[0] in predecessors) { + for (var e of predecessors[edge.Index[0]]) + worklist.push(e); + } + } + if (warnIfNotFound) + printErr("Could not find matching constructor!"); + return undefined; +} + +function pointsInRAIIScope(bodies, body, constructorEdge, limits) { + var seen = {}; + var worklist = [constructorEdge.Index[1]]; + var points = []; + while (worklist.length) { + var point = worklist.pop(); + if (point in seen) + continue; + seen[point] = true; + points.push([body, point, limits]); + var successors = getSuccessors(body); + if (!(point in successors)) + continue; + for (var nedge of successors[point]) { + if (isMatchingDestructor(constructorEdge, nedge)) + continue; + if (nedge.Kind == "Loop") + points.push(...findAllPoints(bodies, nedge.BlockId, limits)); + worklist.push(nedge.Index[1]); + } + } + + return points; +} diff --git a/js/src/devtools/rootAnalysis/Makefile.in b/js/src/devtools/rootAnalysis/Makefile.in new file mode 100644 index 0000000000..e8bc57471a --- /dev/null +++ b/js/src/devtools/rootAnalysis/Makefile.in @@ -0,0 +1,79 @@ +# -*- Mode: makefile -*- +# +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +# This Makefile is used to kick off a static rooting analysis. This Makefile is +# NOT intended for use as part of the standard Mozilla build. Instead, this +# Makefile will use $PATH to subvert compiler invocations to add in the sixgill +# plugin, and then do a regular build of whatever portion of the tree you are +# analyzing. The plugins will dump out several xdb database files. Various +# analysis scripts, written in JS, will run over those database files to +# produce the final analysis output. + +include $(topsrcdir)/config/config.mk + +# Tree to build and analyze, defaulting to the current tree +TARGET_JSOBJDIR ?= $(TOPOBJDIR) + +# Path to a JS binary to use to run the analysis. You really want this to be an +# optimized build. +JS ?= $(DIST)/bin/js + +# Path to an xgill checkout containing the GCC plugin, xdb-processing binaries, +# and compiler wrapper scripts used to automatically integrate into an existing +# build system. +SIXGILL ?= @SIXGILL_PATH@ + +# Path to the JS scripts that will perform the analysis, defaulting to the same +# place as this Makefile.in, which is probably what you want. +ANALYSIS_SCRIPT_DIR ?= $(srcdir) + +# Number of simultanous analyzeRoots.js scripts to run. +JOBS ?= 6 + +all : rootingHazards.txt allFunctions.txt + +CALL_JS := time env PATH=$$PATH:$(SIXGILL)/bin XDB=$(SIXGILL)/bin/xdb.so $(JS) + +src_body.xdb src_comp.xdb: run_complete + @echo Started compilation at $$(date) + $(ANALYSIS_SCRIPT_DIR)/run_complete --foreground --build-root=$(TARGET_JSOBJDIR) --work-dir=work -b $(SIXGILL)/bin $(CURDIR) + @echo Finished compilation at $$(date) + +callgraph.txt: src_body.xdb src_comp.xdb computeCallgraph.js + @echo Started computation of $@ at $$(date) + $(CALL_JS) $(ANALYSIS_SCRIPT_DIR)/computeCallgraph.js > $@.tmp + mv $@.tmp $@ + @echo Finished computation of $@ at $$(date) + +gcFunctions.txt: callgraph.txt computeGCFunctions.js annotations.js + @echo Started computation of $@ at $$(date) + $(CALL_JS) $(ANALYSIS_SCRIPT_DIR)/computeGCFunctions.js ./callgraph.txt > $@.tmp + mv $@.tmp $@ + @echo Finished computation of $@ at $$(date) + +gcFunctions.lst: gcFunctions.txt + perl -lne 'print $$1 if /^GC Function: (.*)/' gcFunctions.txt > $@ + +suppressedFunctions.lst: gcFunctions.txt + perl -lne 'print $$1 if /^Suppressed Function: (.*)/' gcFunctions.txt > $@ + +gcTypes.txt: src_comp.xdb computeGCTypes.js annotations.js + @echo Started computation of $@ at $$(date) + $(CALL_JS) $(ANALYSIS_SCRIPT_DIR)/computeGCTypes.js > $@.tmp + mv $@.tmp $@ + @echo Finished computation of $@ at $$(date) + +allFunctions.txt: src_body.xdb + @echo Started computation of $@ at $$(date) + time $(SIXGILL)/bin/xdbkeys $^ > $@.tmp + mv $@.tmp $@ + @echo Finished computation of $@ at $$(date) + +rootingHazards.txt: gcFunctions.lst suppressedFunctions.lst gcTypes.txt analyzeRoots.js annotations.js gen-hazards.sh + @echo Started computation of $@ at $$(date) + time env JS=$(JS) ANALYZE='$(ANALYSIS_SCRIPT_DIR)/analyzeRoots.js' SIXGILL='$(SIXGILL)' '$(ANALYSIS_SCRIPT_DIR)/gen-hazards.sh' $(JOBS) > $@.tmp + mv $@.tmp $@ + @echo Finished computation of $@ at $$(date) diff --git a/js/src/devtools/rootAnalysis/README.md b/js/src/devtools/rootAnalysis/README.md new file mode 100644 index 0000000000..682345a2c9 --- /dev/null +++ b/js/src/devtools/rootAnalysis/README.md @@ -0,0 +1,109 @@ +# Spidermonkey JSAPI rooting analysis + +This directory contains scripts for running Brian Hackett's static GC rooting +and thread heap write safety analyses on a JS source directory. + +To run the analysis on SpiderMonkey: + +1. Install prerequisites. + + mach hazards bootstrap + +2. Build the shell to run the analysis. + + mach hazards build-shell + +3. Compile all the code to gather info. + + mach hazards gather --application=js + +4. Analyze the gathered info. + + mach hazards analyze --application=js + +Output goes to `haz-js/hazards.txt`. This will run the analysis on the js/src +tree only; if you wish to analyze the full browser, use + + --application=browser + +(or leave it off; `--application=browser` is the default) + +After running the analysis once, you can reuse the `*.xdb` database files +generated, using modified analysis scripts, by running either the `mach hazards +analyze` command above, or with `haz-js/run-analysis.sh` (pass `--list` to see +ways to select even more restrictive parts of the overall analysis; the default +is `gcTypes` which will do everything but regenerate the xdb files). + +Also, you can pass `-v` to get exact command lines to cut & paste for running +the various stages, which is helpful for running under a debugger. + +## Overview of what is going on here + +So what does this actually do? + +1. It downloads a GCC compiler and plugin ("sixgill") from Mozilla servers. + +2. It runs `run_complete`, a script that builds the target codebase with the + downloaded GCC, generating a few database files containing control flow + graphs of the full compile, along with type information etc. + +3. Then it runs `analyze.py`, a Python script, which runs all the scripts + which actually perform the analysis -- the tricky parts. + (Those scripts are written in JS.) + +The easiest way to get this running is to not try to do the instrumented +compilation locally. Instead, grab the relevant files from a try server push +and analyze them locally. + +## Local Analysis of Downloaded Intermediate Files + +Another useful path is to let the continuous integration system do the hard +work of generating the intermediate files and analyze them locally. This is +particularly useful if you are working on the analysis itself. + +1. Do a try push with "--upload-xdbs" appended to the try: ..." line. + + mach try fuzzy -q "'haz" --upload-xdbs + +2. Create an empty directory to run the analysis. + +3. When the try job is complete, download the resulting src_body.xdb.bz2, src_comp.xdb.bz2, +and file_source.xdb.bz2 files into your directory. + +4. Fetch a compiler and sixgill plugin to use: + + mach hazards bootstrap + +If you are on osx, these will not be available. Instead, build sixgill manually +(these directions are a little stale): + + hg clone https://hg.mozilla.org/users/sfink_mozilla.com/sixgill + cd sixgill + CC=$HOME/.mozbuild/hazard-tools/gcc/bin/gcc ./release.sh --build # This will fail horribly. + make bin/xdb.so CXX=clang++ + +5. Build an optimized JS shell with ctypes. Note that this does not need to +match the source you are analyzing in any way; in fact, you pretty much never +need to update this once you've built it. (Though I reserve the right to use +any new JS features implemented in Spidermonkey in the future...) + + mach hazards build-shell + +The shell will be placed by default in $topsrcdir/obj-haz-shell. + +6. Make a defaults.py file containing the following, with your own paths filled in: + + js = "<objdir>/dist/bin/js" + sixgill_bin = "<sixgill-dir>/bin" + +7a. For the rooting analysis, run + + python <srcdir>/js/src/devtools/rootAnalysis/analyze.py gcTypes + +7b. For the heap write analysis, run + + python <srcdir>/js/src/devtools/rootAnalysis/analyze.py heapwrites + +Also, you may wish to run with -v (aka --verbose) to see the exact commands +executed that you can cut & paste if needed. (I use them to run under the JS +debugger when I'm working on the analysis.) diff --git a/js/src/devtools/rootAnalysis/analyze.py b/js/src/devtools/rootAnalysis/analyze.py new file mode 100755 index 0000000000..594e65a1c5 --- /dev/null +++ b/js/src/devtools/rootAnalysis/analyze.py @@ -0,0 +1,414 @@ +#!/usr/bin/python + +# +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +""" +Runs the static rooting analysis +""" + +from subprocess import Popen +import argparse +import os +import subprocess +import sys +import re + +try: + from shlex import quote +except ImportError: + from pipes import quote + +# Python 2/3 version independence polyfills + +anystring_t = str if sys.version_info[0] > 2 else basestring + +try: + execfile +except Exception: + + def execfile(thefile, globals): + exec(compile(open(thefile).read(), filename=thefile, mode="exec"), globals) + + +def env(config): + e = dict(os.environ) + e["PATH"] = ":".join( + p for p in (config.get("gcc_bin"), config.get("sixgill_bin"), e["PATH"]) if p + ) + e["XDB"] = "%(sixgill_bin)s/xdb.so" % config + e["SOURCE"] = config["source"] + e["ANALYZED_OBJDIR"] = config["objdir"] + return e + + +def fill(command, config): + try: + return tuple(s % config for s in command) + except Exception: + print("Substitution failed:") + problems = [] + for fragment in command: + try: + fragment % config + except Exception: + problems.append(fragment) + raise Exception( + "\n".join(["Substitution failed:"] + [" %s" % s for s in problems]) + ) + + +def print_command(command, outfile=None, env=None): + output = " ".join(quote(s) for s in command) + if outfile: + output += " > " + outfile + if env: + changed = {} + e = os.environ + for key, value in env.items(): + if (key not in e) or (e[key] != value): + changed[key] = value + if changed: + outputs = [] + for key, value in changed.items(): + if key in e and e[key] in value: + start = value.index(e[key]) + end = start + len(e[key]) + outputs.append( + '%s="%s${%s}%s"' % (key, value[:start], key, value[end:]) + ) + else: + outputs.append("%s='%s'" % (key, value)) + output = " ".join(outputs) + " " + output + + print(output) + + +def generate_hazards(config, outfilename): + jobs = [] + for i in range(int(config["jobs"])): + command = fill( + ( + "%(js)s", + "%(analysis_scriptdir)s/analyzeRoots.js", + "%(gcFunctions_list)s", + "%(gcEdges)s", + "%(limitedFunctions_list)s", + "%(gcTypes)s", + "%(typeInfo)s", + str(i + 1), + "%(jobs)s", + "tmp.%s" % (i + 1,), + ), + config, + ) + outfile = "rootingHazards.%s" % (i + 1,) + output = open(outfile, "w") + if config["verbose"]: + print_command(command, outfile=outfile, env=env(config)) + jobs.append((command, Popen(command, stdout=output, env=env(config)))) + + final_status = 0 + while jobs: + pid, status = os.wait() + jobs = [job for job in jobs if job[1].pid != pid] + final_status = final_status or status + + if final_status: + raise subprocess.CalledProcessError(final_status, "analyzeRoots.js") + + with open(outfilename, "w") as output: + command = ["cat"] + [ + "rootingHazards.%s" % (i + 1,) for i in range(int(config["jobs"])) + ] + if config["verbose"]: + print_command(command, outfile=outfilename) + subprocess.call(command, stdout=output) + + +JOBS = { + "dbs": ( + ( + "%(analysis_scriptdir)s/run_complete", + "--foreground", + "--no-logs", + "--build-root=%(objdir)s", + "--wrap-dir=%(sixgill)s/scripts/wrap_gcc", + "--work-dir=work", + "-b", + "%(sixgill_bin)s", + "--buildcommand=%(buildcommand)s", + ".", + ), + (), + ), + "list-dbs": (("ls", "-l"), ()), + "callgraph": ( + ( + "%(js)s", + "%(analysis_scriptdir)s/computeCallgraph.js", + "%(typeInfo)s", + "[callgraph]", + ), + ("callgraph.txt",), + ), + "gcFunctions": ( + ( + "%(js)s", + "%(analysis_scriptdir)s/computeGCFunctions.js", + "%(callgraph)s", + "[gcFunctions]", + "[gcFunctions_list]", + "[gcEdges]", + "[limitedFunctions_list]", + ), + ("gcFunctions.txt", "gcFunctions.lst", "gcEdges.txt", "limitedFunctions.lst"), + ), + "gcTypes": ( + ( + "%(js)s", + "%(analysis_scriptdir)s/computeGCTypes.js", + "[gcTypes]", + "[typeInfo]", + ), + ("gcTypes.txt", "typeInfo.txt"), + ), + "allFunctions": ( + ( + "%(sixgill_bin)s/xdbkeys", + "src_body.xdb", + ), + "allFunctions.txt", + ), + "hazards": (generate_hazards, "rootingHazards.txt"), + "explain": ( + ( + os.environ.get("PYTHON", "python2.7"), + "%(analysis_scriptdir)s/explain.py", + "%(hazards)s", + "%(gcFunctions)s", + "[explained_hazards]", + "[unnecessary]", + "[refs]", + ), + ("hazards.txt", "unnecessary.txt", "refs.txt"), + ), + "heapwrites": ( + ("%(js)s", "%(analysis_scriptdir)s/analyzeHeapWrites.js"), + "heapWriteHazards.txt", + ), +} + + +def out_indexes(command): + for i in range(len(command)): + m = re.match(r"^\[(.*)\]$", command[i]) + if m: + yield (i, m.group(1)) + + +def run_job(name, config): + cmdspec, outfiles = JOBS[name] + print("Running " + name + " to generate " + str(outfiles)) + if hasattr(cmdspec, "__call__"): + cmdspec(config, outfiles) + else: + temp_map = {} + cmdspec = fill(cmdspec, config) + if isinstance(outfiles, anystring_t): + stdout_filename = "%s.tmp" % name + temp_map[stdout_filename] = outfiles + if config["verbose"]: + print_command(cmdspec, outfile=outfiles, env=env(config)) + else: + stdout_filename = None + pc = list(cmdspec) + outfile = 0 + for (i, name) in out_indexes(cmdspec): + pc[i] = outfiles[outfile] + outfile += 1 + if config["verbose"]: + print_command(pc, env=env(config)) + + command = list(cmdspec) + outfile = 0 + for (i, name) in out_indexes(cmdspec): + command[i] = "%s.tmp" % name + temp_map[command[i]] = outfiles[outfile] + outfile += 1 + + sys.stdout.flush() + if stdout_filename is None: + subprocess.check_call(command, env=env(config)) + else: + with open(stdout_filename, "w") as output: + subprocess.check_call(command, stdout=output, env=env(config)) + for (temp, final) in temp_map.items(): + try: + os.rename(temp, final) + except OSError: + print("Error renaming %s -> %s" % (temp, final)) + raise + + +config = {"analysis_scriptdir": os.path.dirname(__file__)} + +defaults = [ + "%s/defaults.py" % config["analysis_scriptdir"], + "%s/defaults.py" % os.getcwd(), +] + +parser = argparse.ArgumentParser( + description="Statically analyze build tree for rooting hazards." +) +parser.add_argument( + "step", metavar="STEP", type=str, nargs="?", help="run starting from this step" +) +parser.add_argument( + "--source", metavar="SOURCE", type=str, nargs="?", help="source code to analyze" +) +parser.add_argument( + "--objdir", + metavar="DIR", + type=str, + nargs="?", + help="object directory of compiled files", +) +parser.add_argument( + "--js", + metavar="JSSHELL", + type=str, + nargs="?", + help="full path to ctypes-capable JS shell", +) +parser.add_argument( + "--upto", metavar="UPTO", type=str, nargs="?", help="last step to execute" +) +parser.add_argument( + "--jobs", + "-j", + default=None, + metavar="JOBS", + type=int, + help="number of simultaneous analyzeRoots.js jobs", +) +parser.add_argument( + "--list", const=True, nargs="?", type=bool, help="display available steps" +) +parser.add_argument( + "--buildcommand", + "--build", + "-b", + type=str, + nargs="?", + help="command to build the tree being analyzed", +) +parser.add_argument( + "--tag", + "-t", + type=str, + nargs="?", + help='name of job, also sets build command to "build.<tag>"', +) +parser.add_argument( + "--expect-file", + type=str, + nargs="?", + help="deprecated option, temporarily still present for backwards " "compatibility", +) +parser.add_argument( + "--verbose", + "-v", + action="count", + default=1, + help="Display cut & paste commands to run individual steps", +) +parser.add_argument("--quiet", "-q", action="count", default=0, help="Suppress output") + +args = parser.parse_args() +args.verbose = max(0, args.verbose - args.quiet) + +for default in defaults: + try: + execfile(default, config) + if args.verbose: + print("Loaded %s" % default) + except Exception: + pass + +data = config.copy() + +for k, v in vars(args).items(): + if v is not None: + data[k] = v + +if args.tag and not args.buildcommand: + args.buildcommand = "build.%s" % args.tag + +if args.jobs is not None: + data["jobs"] = args.jobs +if not data.get("jobs"): + data["jobs"] = int(subprocess.check_output(["nproc", "--ignore=1"]).strip()) + +if args.buildcommand: + data["buildcommand"] = args.buildcommand +elif "BUILD" in os.environ: + data["buildcommand"] = os.environ["BUILD"] +else: + data["buildcommand"] = "make -j4 -s" + +if "ANALYZED_OBJDIR" in os.environ: + data["objdir"] = os.environ["ANALYZED_OBJDIR"] + +if "GECKO_PATH" in os.environ: + data["source"] = os.environ["GECKO_PATH"] +if "SOURCE" in os.environ: + data["source"] = os.environ["SOURCE"] + +steps = [ + "dbs", + "gcTypes", + "callgraph", + "gcFunctions", + "allFunctions", + "hazards", + "explain", + "heapwrites", +] + +if args.list: + for step in steps: + command, outfilename = JOBS[step] + if outfilename: + print("%s -> %s" % (step, outfilename)) + else: + print(step) + sys.exit(0) + +for step in steps: + command, outfiles = JOBS[step] + if isinstance(outfiles, anystring_t): + data[step] = outfiles + else: + outfile = 0 + for (i, name) in out_indexes(command): + data[name] = outfiles[outfile] + outfile += 1 + assert ( + len(outfiles) == outfile + ), "step '%s': mismatched number of output files (%d) and params (%d)" % ( + step, + outfile, + len(outfiles), + ) # NOQA: E501 + +if args.step: + steps = steps[steps.index(args.step) :] + +if args.upto: + steps = steps[: steps.index(args.upto) + 1] + +for step in steps: + run_job(step, data) diff --git a/js/src/devtools/rootAnalysis/analyzeHeapWrites.js b/js/src/devtools/rootAnalysis/analyzeHeapWrites.js new file mode 100644 index 0000000000..cb757f9882 --- /dev/null +++ b/js/src/devtools/rootAnalysis/analyzeHeapWrites.js @@ -0,0 +1,1404 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +loadRelativeToScript('utility.js'); +loadRelativeToScript('annotations.js'); +loadRelativeToScript('callgraph.js'); +loadRelativeToScript('dumpCFG.js'); + +/////////////////////////////////////////////////////////////////////////////// +// Annotations +/////////////////////////////////////////////////////////////////////////////// + +function checkExternalFunction(entry) +{ + var whitelist = [ + "__builtin_clz", + "__builtin_expect", + "isprint", + "ceilf", + "floorf", + /^rusturl/, + "memcmp", + "strcmp", + "fmod", + "floor", + "ceil", + "atof", + /memchr/, + "strlen", + /Servo_DeclarationBlock_GetCssText/, + "Servo_GetArcStringData", + "Servo_IsWorkerThread", + /nsIFrame::AppendOwnedAnonBoxes/, + // Assume that atomic accesses are threadsafe. + /^__atomic_/, + ]; + if (entry.matches(whitelist)) + return; + + // memcpy and memset are safe if the target pointer is threadsafe. + const simpleWrites = [ + "memcpy", + "memset", + "memmove", + ]; + + if (entry.isSafeArgument(1) && simpleWrites.includes(entry.name)) + return; + + dumpError(entry, null, "External function"); +} + +function hasThreadsafeReferenceCounts(entry, regexp) +{ + // regexp should match some nsISupports-operating function and produce the + // name of the nsISupports class via exec(). + + // nsISupports classes which have threadsafe reference counting. + var whitelist = [ + "nsIRunnable", + + // I don't know if these always have threadsafe refcounts. + "nsAtom", + "nsIPermissionManager", + "nsIURI", + ]; + + var match = regexp.exec(entry.name); + return match && nameMatchesArray(match[1], whitelist); +} + +function checkOverridableVirtualCall(entry, location, callee) +{ + // We get here when a virtual call is made on a structure which might be + // overridden by script or by a binary extension. This includes almost + // everything under nsISupports, however, so for the most part we ignore + // this issue. The exception is for nsISupports AddRef/Release, which are + // not in general threadsafe and whose overrides will not be generated by + // the callgraph analysis. + if (callee != "nsISupports.AddRef" && callee != "nsISupports.Release") + return; + + if (hasThreadsafeReferenceCounts(entry, /::~?nsCOMPtr\(.*?\[with T = (.*?)\]$/)) + return; + if (hasThreadsafeReferenceCounts(entry, /RefPtrTraits.*?::Release.*?\[with U = (.*?)\]/)) + return; + if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::assign_assuming_AddRef.*?\[with T = (.*?)\]/)) + return; + if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::assign_with_AddRef.*?\[with T = (.*?)\]/)) + return; + + // Watch for raw addref/release. + var whitelist = [ + "Gecko_AddRefAtom", + "Gecko_ReleaseAtom", + /nsPrincipal::Get/, + /CounterStylePtr::Reset/, + ]; + if (entry.matches(whitelist)) + return; + + dumpError(entry, location, "AddRef/Release on nsISupports"); +} + +function checkIndirectCall(entry, location, callee) +{ + var name = entry.name; + + // These hash table callbacks should be threadsafe. + if (/PLDHashTable/.test(name) && (/matchEntry/.test(callee) || /hashKey/.test(callee))) + return; + if (/PL_HashTable/.test(name) && /keyCompare/.test(callee)) + return; + + dumpError(entry, location, "Indirect call " + callee); +} + +function checkVariableAssignment(entry, location, variable) +{ + var name = entry.name; + + dumpError(entry, location, "Variable assignment " + variable); +} + +// Annotations for function parameters, based on function name and parameter +// name + type. +function treatAsSafeArgument(entry, varName, csuName) +{ + var whitelist = [ + // These iterator classes should all be thread local. They are passed + // in to some Servo bindings and are created on the heap by others, so + // just ignore writes to them. + [null, null, /StyleChildrenIterator/], + [null, null, /ExplicitChildIterator/], + + // The use of BeginReading() to instantiate this class confuses the + // analysis. + [null, null, /nsReadingIterator/], + + // These classes are passed to some Servo bindings to fill in. + [/^Gecko_/, null, "nsStyleImageLayers"], + [/^Gecko_/, null, /FontFamilyList/], + + // RawGeckoBorrowedNode thread-mutable parameters. + ["Gecko_SetNodeFlags", "aNode", null], + ["Gecko_UnsetNodeFlags", "aNode", null], + + // Various Servo binding out parameters. This is a mess and there needs + // to be a way to indicate which params are out parameters, either using + // an attribute or a naming convention. + ["Gecko_CopyAnimationNames", "aDest", null], + ["Gecko_CopyFontFamilyFrom", "dst", null], + ["Gecko_SetAnimationName", "aStyleAnimation", null], + ["Gecko_SetCounterStyleToName", "aPtr", null], + ["Gecko_SetCounterStyleToSymbols", "aPtr", null], + ["Gecko_SetCounterStyleToString", "aPtr", null], + ["Gecko_CopyCounterStyle", "aDst", null], + ["Gecko_SetMozBinding", "aDisplay", null], + [/ClassOrClassList/, /aClass/, null], + ["Gecko_GetAtomAsUTF16", "aLength", null], + ["Gecko_CopyMozBindingFrom", "aDest", null], + ["Gecko_SetNullImageValue", "aImage", null], + ["Gecko_SetGradientImageValue", "aImage", null], + ["Gecko_SetImageElement", "aImage", null], + ["Gecko_SetLayerImageImageValue", "aImage", null], + ["Gecko_CopyImageValueFrom", "aImage", null], + ["Gecko_SetCursorArrayLength", "aStyleUI", null], + ["Gecko_CopyCursorArrayFrom", "aDest", null], + ["Gecko_SetCursorImageValue", "aCursor", null], + ["Gecko_SetListStyleImageImageValue", "aList", null], + ["Gecko_SetListStyleImageNone", "aList", null], + ["Gecko_CopyListStyleImageFrom", "aList", null], + ["Gecko_ClearStyleContents", "aContent", null], + ["Gecko_CopyStyleContentsFrom", "aContent", null], + ["Gecko_CopyStyleGridTemplateValues", "aGridTemplate", null], + ["Gecko_ResetStyleCoord", null, null], + ["Gecko_CopyClipPathValueFrom", "aDst", null], + ["Gecko_DestroyClipPath", "aClip", null], + ["Gecko_ResetFilters", "effects", null], + ["Gecko_CopyFiltersFrom", "aDest", null], + [/Gecko_CSSValue_Set/, "aCSSValue", null], + ["Gecko_CSSValue_Drop", "aCSSValue", null], + ["Gecko_CSSFontFaceRule_GetCssText", "aResult", null], + ["Gecko_EnsureTArrayCapacity", "aArray", null], + ["Gecko_ClearPODTArray", "aArray", null], + ["Gecko_SetStyleGridTemplate", "aGridTemplate", null], + ["Gecko_ResizeTArrayForStrings", "aArray", null], + ["Gecko_ClearAndResizeStyleContents", "aContent", null], + [/Gecko_ClearAndResizeCounter/, "aContent", null], + [/Gecko_CopyCounter.*?From/, "aContent", null], + [/Gecko_SetContentDataImageValue/, "aList", null], + [/Gecko_SetContentData/, "aContent", null], + ["Gecko_SetCounterFunction", "aContent", null], + [/Gecko_EnsureStyle.*?ArrayLength/, "aArray", null], + ["Gecko_GetOrCreateKeyframeAtStart", "aKeyframes", null], + ["Gecko_GetOrCreateInitialKeyframe", "aKeyframes", null], + ["Gecko_GetOrCreateFinalKeyframe", "aKeyframes", null], + ["Gecko_AppendPropertyValuePair", "aProperties", null], + ["Gecko_SetStyleCoordCalcValue", null, null], + ["Gecko_StyleClipPath_SetURLValue", "aClip", null], + ["Gecko_nsStyleFilter_SetURLValue", "aEffects", null], + ["Gecko_nsStyleSVG_SetDashArrayLength", "aSvg", null], + ["Gecko_nsStyleSVG_CopyDashArray", "aDst", null], + ["Gecko_nsStyleFont_SetLang", "aFont", null], + ["Gecko_nsStyleFont_CopyLangFrom", "aFont", null], + ["Gecko_ClearWillChange", "aDisplay", null], + ["Gecko_AppendWillChange", "aDisplay", null], + ["Gecko_CopyWillChangeFrom", "aDest", null], + ["Gecko_InitializeImageCropRect", "aImage", null], + ["Gecko_CopyShapeSourceFrom", "aDst", null], + ["Gecko_DestroyShapeSource", "aShape", null], + ["Gecko_StyleShapeSource_SetURLValue", "aShape", null], + ["Gecko_NewBasicShape", "aShape", null], + ["Gecko_NewShapeImage", "aShape", null], + ["Gecko_nsFont_InitSystem", "aDest", null], + ["Gecko_nsFont_SetFontFeatureValuesLookup", "aFont", null], + ["Gecko_nsFont_ResetFontFeatureValuesLookup", "aFont", null], + ["Gecko_nsStyleFont_FixupNoneGeneric", "aFont", null], + ["Gecko_StyleTransition_SetUnsupportedProperty", "aTransition", null], + ["Gecko_AddPropertyToSet", "aPropertySet", null], + ["Gecko_CalcStyleDifference", "aAnyStyleChanged", null], + ["Gecko_CalcStyleDifference", "aOnlyResetStructsChanged", null], + ["Gecko_nsStyleSVG_CopyContextProperties", "aDst", null], + ["Gecko_nsStyleFont_PrefillDefaultForGeneric", "aFont", null], + ["Gecko_nsStyleSVG_SetContextPropertiesLength", "aSvg", null], + ["Gecko_ClearAlternateValues", "aFont", null], + ["Gecko_AppendAlternateValues", "aFont", null], + ["Gecko_CopyAlternateValuesFrom", "aDest", null], + ["Gecko_CounterStyle_GetName", "aResult", null], + ["Gecko_CounterStyle_GetSingleString", "aResult", null], + ["Gecko_nsTArray_FontFamilyName_AppendNamed", "aNames", null], + ["Gecko_nsTArray_FontFamilyName_AppendGeneric", "aNames", null], + ]; + for (var [entryMatch, varMatch, csuMatch] of whitelist) { + assert(entryMatch || varMatch || csuMatch); + if (entryMatch && !nameMatches(entry.name, entryMatch)) + continue; + if (varMatch && !nameMatches(varName, varMatch)) + continue; + if (csuMatch && (!csuName || !nameMatches(csuName, csuMatch))) + continue; + return true; + } + return false; +} + +function isSafeAssignment(entry, edge, variable) +{ + if (edge.Kind != 'Assign') + return false; + + var [mangled, unmangled] = splitFunction(entry.name); + + // The assignment + // + // nsFont* font = fontTypes[eType]; + // + // ends up with 'font' pointing to a member of 'this', so it should inherit + // the safety of 'this'. + if (unmangled.includes("mozilla::LangGroupFontPrefs::Initialize") && + variable == 'font') + { + const [lhs, rhs] = edge.Exp; + const {Kind, Exp: [{Kind: indexKind, Exp: [collection, index]}]} = rhs; + if (Kind == 'Drf' && + indexKind == 'Index' && + collection.Kind == 'Var' && + collection.Variable.Name[0] == 'fontTypes') + { + return entry.isSafeArgument(0); // 'this' + } + } + + return false; +} + +function checkFieldWrite(entry, location, fields) +{ + var name = entry.name; + for (var field of fields) { + // The analysis is having some trouble keeping track of whether + // already_AddRefed and nsCOMPtr structures are safe to access. + // Hopefully these will be thread local, but it would be better to + // improve the analysis to handle these. + if (/already_AddRefed.*?.mRawPtr/.test(field)) + return; + if (/nsCOMPtr<.*?>.mRawPtr/.test(field)) + return; + + if (/\bThreadLocal<\b/.test(field)) + return; + + // Debugging check for string corruption. + if (field == "nsStringBuffer.mCanary") + return; + } + + var str = ""; + for (var field of fields) + str += " " + field; + + dumpError(entry, location, "Field write" + str); +} + +function checkDereferenceWrite(entry, location, variable) +{ + var name = entry.name; + + // Maybe<T> uses placement new on local storage in a way we don't understand. + // Allow this if the Maybe<> value itself is threadsafe. + if (/Maybe.*?::emplace/.test(name) && entry.isSafeArgument(0)) + return; + + // UniquePtr writes through temporaries referring to its internal storage. + // Allow this if the UniquePtr<> is threadsafe. + if (/UniquePtr.*?::reset/.test(name) && entry.isSafeArgument(0)) + return; + + // Operations on nsISupports reference counts. + if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::swap\(.*?\[with T = (.*?)\]/)) + return; + + // ConvertToLowerCase::write writes through a local pointer into the first + // argument. + if (/ConvertToLowerCase::write/.test(name) && entry.isSafeArgument(0)) + return; + + dumpError(entry, location, "Dereference write " + (variable ? variable : "<unknown>")); +} + +function ignoreCallEdge(entry, callee) +{ + var name = entry.name; + + // nsPropertyTable::GetPropertyInternal has the option of removing data + // from the table, but when it is called by nsPropertyTable::GetProperty + // this will not occur. + if (/nsPropertyTable::GetPropertyInternal/.test(callee) && + /nsPropertyTable::GetProperty/.test(name)) + { + return true; + } + + // Document::PropertyTable calls GetExtraPropertyTable (which has side + // effects) if the input category is non-zero. If a literal zero was passed + // in for the category then we treat it as a safe argument, per + // isEdgeSafeArgument, so just watch for that. + if (/Document::GetExtraPropertyTable/.test(callee) && + /Document::PropertyTable/.test(name) && + entry.isSafeArgument(1)) + { + return true; + } + + // This function has an explicit test for being on the main thread if the + // style has non-threadsafe refcounts, but the analysis isn't smart enough + // to understand what the actual styles that can be involved are. + if (/nsStyleList::SetCounterStyle/.test(callee)) + return true; + + // CachedBorderImageData is exclusively owned by nsStyleImage, but the + // analysis is not smart enough to know this. + if (/CachedBorderImageData::PurgeCachedImages/.test(callee) && + /nsStyleImage::/.test(name) && + entry.isSafeArgument(0)) + { + return true; + } + + // StyleShapeSource exclusively owns its UniquePtr<nsStyleImage>. + if (/nsStyleImage::SetURLValue/.test(callee) && + /StyleShapeSource::SetURL/.test(name) && + entry.isSafeArgument(0)) + { + return true; + } + + // The AddRef through a just-assigned heap pointer here is not handled by + // the analysis. + if (/nsCSSValue::Array::AddRef/.test(callee) && + /nsStyleContentData::SetCounters/.test(name) && + entry.isSafeArgument(2)) + { + return true; + } + + // AllChildrenIterator asks AppendOwnedAnonBoxes to append into an nsTArray + // local variable. + if (/nsIFrame::AppendOwnedAnonBoxes/.test(callee) && + /AllChildrenIterator::AppendNativeAnonymousChildren/.test(name)) + { + return true; + } + + // Runnables are created and named on one thread, then dispatched + // (possibly to another). Writes on the origin thread are ok. + if (/::SetName/.test(callee) && + /::UnlabeledDispatch/.test(name)) + { + return true; + } + + // We manually lock here + if (name == "Gecko_nsFont_InitSystem" || + name == "Gecko_GetFontMetrics" || + name == "Gecko_nsStyleFont_FixupMinFontSize" || + /ThreadSafeGetDefaultFontHelper/.test(name)) + { + return true; + } + + return false; +} + +function ignoreContents(entry) +{ + var whitelist = [ + // We don't care what happens when we're about to crash. + "abort", + /MOZ_ReportAssertionFailure/, + /MOZ_ReportCrash/, + /MOZ_Crash/, + /MOZ_CrashPrintf/, + /AnnotateMozCrashReason/, + /InvalidArrayIndex_CRASH/, + /NS_ABORT_OOM/, + + // These ought to be threadsafe. + "NS_DebugBreak", + /mozalloc_handle_oom/, + /^NS_Log/, /log_print/, /LazyLogModule::operator/, + /SprintfLiteral/, "PR_smprintf", "PR_smprintf_free", + /NS_DispatchToMainThread/, /NS_ReleaseOnMainThread/, + /NS_NewRunnableFunction/, /NS_Atomize/, + /nsCSSValue::BufferFromString/, + /NS_xstrdup/, + /Assert_NoQueryNeeded/, + /AssertCurrentThreadOwnsMe/, + /PlatformThread::CurrentId/, + /imgRequestProxy::GetProgressTracker/, // Uses an AutoLock + /Smprintf/, + "malloc", + "calloc", + "free", + "realloc", + "memalign", + "strdup", + "strndup", + "moz_xmalloc", + "moz_xcalloc", + "moz_xrealloc", + "moz_xmemalign", + "moz_xstrdup", + "moz_xstrndup", + "jemalloc_thread_local_arena", + + // These all create static strings in local storage, which is threadsafe + // to do but not understood by the analysis yet. + / EmptyString\(\)/, + + // These could probably be handled by treating the scope of PSAutoLock + // aka BaseAutoLock<PSMutex> as threadsafe. + /profiler_register_thread/, + /profiler_unregister_thread/, + + // The analysis thinks we'll write to mBits in the DoGetStyleFoo<false> + // call. Maybe the template parameter confuses it? + /ComputedStyle::PeekStyle/, + + // The analysis can't cope with the indirection used for the objects + // being initialized here, from nsCSSValue::Array::Create to the return + // value of the Item(i) getter. + /nsCSSValue::SetCalcValue/, + + // Unable to analyze safety of linked list initialization. + "Gecko_NewCSSValueSharedList", + "Gecko_CSSValue_InitSharedList", + + // Unable to trace through dataflow, but straightforward if inspected. + "Gecko_NewNoneTransform", + + // Need main thread assertions or other fixes. + /EffectCompositor::GetServoAnimationRule/, + ]; + if (entry.matches(whitelist)) + return true; + + if (entry.isSafeArgument(0)) { + var heapWhitelist = [ + // Operations on heap structures pointed to by arrays and strings are + // threadsafe as long as the array/string itself is threadsafe. + /nsTArray_Impl.*?::AppendElement/, + /nsTArray_Impl.*?::RemoveElementsAt/, + /nsTArray_Impl.*?::ReplaceElementsAt/, + /nsTArray_Impl.*?::InsertElementAt/, + /nsTArray_Impl.*?::SetCapacity/, + /nsTArray_Impl.*?::SetLength/, + /nsTArray_base.*?::EnsureCapacity/, + /nsTArray_base.*?::ShiftData/, + /AutoTArray.*?::Init/, + /(nsTSubstring<T>|nsAC?String)::SetCapacity/, + /(nsTSubstring<T>|nsAC?String)::SetLength/, + /(nsTSubstring<T>|nsAC?String)::Assign/, + /(nsTSubstring<T>|nsAC?String)::Append/, + /(nsTSubstring<T>|nsAC?String)::Replace/, + /(nsTSubstring<T>|nsAC?String)::Trim/, + /(nsTSubstring<T>|nsAC?String)::Truncate/, + /(nsTSubstring<T>|nsAC?String)::StripTaggedASCII/, + /(nsTSubstring<T>|nsAC?String)::operator=/, + /nsTAutoStringN<T, N>::nsTAutoStringN/, + + // Similar for some other data structures + /nsCOMArray_base::SetCapacity/, + /nsCOMArray_base::Clear/, + /nsCOMArray_base::AppendElement/, + + // UniquePtr is similar. + /mozilla::UniquePtr/, + + // The use of unique pointers when copying mCropRect here confuses + // the analysis. + /nsStyleImage::DoCopy/, + ]; + if (entry.matches(heapWhitelist)) + return true; + } + + if (entry.isSafeArgument(1)) { + var firstArgWhitelist = [ + /nsTextFormatter::snprintf/, + /nsTextFormatter::ssprintf/, + /_ASCIIToUpperInSitu/, + + // Handle some writes into an array whose safety we don't have a good way + // of tracking currently. + /FillImageLayerList/, + /FillImageLayerPositionCoordList/, + ]; + if (entry.matches(firstArgWhitelist)) + return true; + } + + if (entry.isSafeArgument(2)) { + var secondArgWhitelist = [ + /nsStringBuffer::ToString/, + /AppendUTF\d+toUTF\d+/, + /AppendASCIItoUTF\d+/, + ]; + if (entry.matches(secondArgWhitelist)) + return true; + } + + return false; +} + +/////////////////////////////////////////////////////////////////////////////// +// Sixgill Utilities +/////////////////////////////////////////////////////////////////////////////// + +function variableName(variable) +{ + return (variable && variable.Name) ? variable.Name[0] : null; +} + +function stripFields(exp) +{ + // Fields and index operations do not involve any dereferences. Remove them + // from the expression but remember any encountered fields for use by + // annotations later on. + var fields = []; + while (true) { + if (exp.Kind == "Index") { + exp = exp.Exp[0]; + continue; + } + if (exp.Kind == "Fld") { + var csuName = exp.Field.FieldCSU.Type.Name; + var fieldName = exp.Field.Name[0]; + assert(csuName && fieldName); + fields.push(csuName + "." + fieldName); + exp = exp.Exp[0]; + continue; + } + break; + } + return [exp, fields]; +} + +function isLocalVariable(variable) +{ + switch (variable.Kind) { + case "Return": + case "Temp": + case "Local": + case "Arg": + return true; + } + return false; +} + +function isDirectCall(edge, regexp) +{ + return edge.Kind == "Call" + && edge.Exp[0].Kind == "Var" + && regexp.test(variableName(edge.Exp[0].Variable)); +} + +function isZero(exp) +{ + return exp.Kind == "Int" && exp.String == "0"; +} + +/////////////////////////////////////////////////////////////////////////////// +// Analysis Structures +/////////////////////////////////////////////////////////////////////////////// + +// Safe arguments are those which may be written through (directly, not through +// pointer fields etc.) without concerns about thread safety. This includes +// pointers to stack data, null pointers, and other data we know is thread +// local, such as certain arguments to the root functions. +// +// Entries in the worklist keep track of the pointer arguments to the function +// which are safe using a sorted array, so that this can be propagated down the +// stack. Zero is |this|, and arguments are indexed starting at one. + +function WorklistEntry(name, safeArguments, stack, parameterNames) +{ + this.name = name; + this.safeArguments = safeArguments; + this.stack = stack; + this.parameterNames = parameterNames; +} + +WorklistEntry.prototype.readable = function() +{ + const [ mangled, readable ] = splitFunction(this.name); + return readable; +} + +WorklistEntry.prototype.mangledName = function() +{ + var str = this.name; + for (var safe of this.safeArguments) + str += " SAFE " + safe; + return str; +} + +WorklistEntry.prototype.isSafeArgument = function(index) +{ + for (var safe of this.safeArguments) { + if (index == safe) + return true; + } + return false; +} + +WorklistEntry.prototype.setParameterName = function(index, name) +{ + this.parameterNames[index] = name; +} + +WorklistEntry.prototype.addSafeArgument = function(index) +{ + if (this.isSafeArgument(index)) + return; + this.safeArguments.push(index); + + // Sorting isn't necessary for correctness but makes printed stack info tidier. + this.safeArguments.sort(); +} + +function safeArgumentIndex(variable) +{ + if (variable.Kind == "This") + return 0; + if (variable.Kind == "Arg") + return variable.Index + 1; + return -1; +} + +function nameMatches(name, match) +{ + if (typeof match == "string") { + if (name == match) + return true; + } else { + assert(match instanceof RegExp); + if (match.test(name)) + return true; + } + return false; +} + +function nameMatchesArray(name, matchArray) +{ + for (var match of matchArray) { + if (nameMatches(name, match)) + return true; + } + return false; +} + +WorklistEntry.prototype.matches = function(matchArray) +{ + return nameMatchesArray(this.name, matchArray); +} + +function CallSite(callee, safeArguments, location, parameterNames) +{ + this.callee = callee; + this.safeArguments = safeArguments; + this.location = location; + this.parameterNames = parameterNames; +} + +CallSite.prototype.safeString = function() +{ + if (this.safeArguments.length) { + var str = ""; + for (var i = 0; i < this.safeArguments.length; i++) { + var arg = this.safeArguments[i]; + if (arg in this.parameterNames) + str += " " + this.parameterNames[arg]; + else + str += " <" + ((arg == 0) ? "this" : "arg" + (arg - 1)) + ">"; + } + return " ### SafeArguments:" + str; + } + return ""; +} + +/////////////////////////////////////////////////////////////////////////////// +// Analysis Core +/////////////////////////////////////////////////////////////////////////////// + +var errorCount = 0; +var errorLimit = 100; + +// We want to suppress output for functions that ended up not having any +// hazards, for brevity of the final output. So each new toplevel function will +// initialize this to a string, which should be printed only if an error is +// seen. +var errorHeader; + +var startTime = new Date; +function elapsedTime() +{ + var seconds = (new Date - startTime) / 1000; + return "[" + seconds.toFixed(2) + "s] "; +} + +var options = parse_options([ + { + name: '--strip-prefix', + default: os.getenv('SOURCE') || '', + type: 'string' + }, + { + name: '--add-prefix', + default: os.getenv('URLPREFIX') || '', + type: 'string' + }, + { + name: '--verbose', + type: 'bool' + }, +]); + +function add_trailing_slash(str) { + if (str == '') + return str; + return str.endsWith("/") ? str : str + "/"; +} + +var removePrefix = add_trailing_slash(options.strip_prefix); +var addPrefix = add_trailing_slash(options.add_prefix); + +if (options.verbose) { + printErr(`Removing prefix ${removePrefix} from paths`); + printErr(`Prepending ${addPrefix} to paths`); +} + +print(elapsedTime() + "Loading types..."); +if (os.getenv("TYPECACHE")) + loadTypesWithCache('src_comp.xdb', os.getenv("TYPECACHE")); +else + loadTypes('src_comp.xdb'); +print(elapsedTime() + "Starting analysis..."); + +var xdb = xdbLibrary(); +xdb.open("src_body.xdb"); + +var minStream = xdb.min_data_stream(); +var maxStream = xdb.max_data_stream(); +var roots = []; + +var [flag, arg] = scriptArgs; +if (flag && (flag == '-f' || flag == '--function')) { + roots = [arg]; +} else { + for (var bodyIndex = minStream; bodyIndex <= maxStream; bodyIndex++) { + var key = xdb.read_key(bodyIndex); + var name = key.readString(); + if (/^Gecko_/.test(name)) { + var data = xdb.read_entry(key); + if (/ServoBindings.cpp/.test(data.readString())) + roots.push(name); + xdb.free_string(data); + } + xdb.free_string(key); + } +} + +print(elapsedTime() + "Found " + roots.length + " roots."); +for (var i = 0; i < roots.length; i++) { + var root = roots[i]; + errorHeader = elapsedTime() + "#" + (i + 1) + " Analyzing " + root + " ..."; + try { + processRoot(root); + } catch (e) { + if (e != "Error!") + throw e; + } +} + +print(`${elapsedTime()}Completed analysis, found ${errorCount}/${errorLimit} allowed errors`); + +var currentBody; + +// All local variable assignments we have seen in either the outer or inner +// function. This crosses loop boundaries, and currently has an unsoundness +// where later assignments in a loop are not taken into account. +var assignments; + +// All loops in the current function which are reachable off main thread. +var reachableLoops; + +// Functions that are reachable from the current root. +var reachable = {}; + +function dumpError(entry, location, text) +{ + if (errorHeader) { + print(errorHeader); + errorHeader = undefined; + } + + var stack = entry.stack; + print("Error: " + text); + print("Location: " + entry.name + (location ? " @ " + location : "") + stack[0].safeString()); + print("Stack Trace:"); + // Include the callers in the stack trace instead of the callees. Make sure + // the dummy stack entry we added for the original roots is in place. + assert(stack[stack.length - 1].location == null); + for (var i = 0; i < stack.length - 1; i++) + print(stack[i + 1].callee + " @ " + stack[i].location + stack[i + 1].safeString()); + print("\n"); + + if (++errorCount == errorLimit) { + print("Maximum number of errors encountered, exiting..."); + quit(); + } + + throw "Error!"; +} + +// If edge is an assignment from a local variable, return the rhs variable. +function variableAssignRhs(edge) +{ + if (edge.Kind == "Assign" && edge.Exp[1].Kind == "Drf" && edge.Exp[1].Exp[0].Kind == "Var") { + var variable = edge.Exp[1].Exp[0].Variable; + if (isLocalVariable(variable)) + return variable; + } + return null; +} + +function processAssign(body, entry, location, lhs, edge) +{ + var fields; + [lhs, fields] = stripFields(lhs); + + switch (lhs.Kind) { + case "Var": + var name = variableName(lhs.Variable); + if (isLocalVariable(lhs.Variable)) { + // Remember any assignments to local variables in this function. + // Note that we ignore any points where the variable's address is + // taken and indirect assignments might occur. This is an + // unsoundness in the analysis. + + let assign = [body, edge]; + + // Chain assignments if the RHS has only been assigned once. + var rhsVariable = variableAssignRhs(edge); + if (rhsVariable) { + var rhsAssign = singleAssignment(variableName(rhsVariable)); + if (rhsAssign) + assign = rhsAssign; + } + + if (!(name in assignments)) + assignments[name] = []; + assignments[name].push(assign); + } else { + checkVariableAssignment(entry, location, name); + } + return; + case "Drf": + var variable = null; + if (lhs.Exp[0].Kind == "Var") { + variable = lhs.Exp[0].Variable; + if (isSafeVariable(entry, variable)) + return; + } else if (lhs.Exp[0].Kind == "Fld") { + const { + Name: [ fieldName ], + Type: {Kind, Type: fieldType}, + FieldCSU: {Type: {Kind: containerTypeKind, + Name: containerTypeName}} + } = lhs.Exp[0].Field; + const [containerExpr] = lhs.Exp[0].Exp; + + if (containerTypeKind == 'CSU' && + Kind == 'Pointer' && + isEdgeSafeArgument(entry, containerExpr) && + isSafeMemberPointer(containerTypeName, fieldName, fieldType)) + { + return; + } + } + if (fields.length) + checkFieldWrite(entry, location, fields); + else + checkDereferenceWrite(entry, location, variableName(variable)); + return; + case "Int": + if (isZero(lhs)) { + // This shows up under MOZ_ASSERT, to crash the process. + return; + } + } + dumpError(entry, location, "Unknown assignment " + JSON.stringify(lhs)); +} + +function get_location(rawLocation) { + const filename = rawLocation.CacheString.replace(removePrefix, ''); + return addPrefix + filename + "#" + rawLocation.Line; +} + +function process(entry, body, addCallee) +{ + if (!("PEdge" in body)) + return; + + // Add any arguments which are safe due to annotations. + if ("DefineVariable" in body) { + for (var defvar of body.DefineVariable) { + var index = safeArgumentIndex(defvar.Variable); + if (index >= 0) { + var varName = index ? variableName(defvar.Variable) : "this"; + assert(varName); + entry.setParameterName(index, varName); + var csuName = null; + var type = defvar.Type; + if (type.Kind == "Pointer" && type.Type.Kind == "CSU") + csuName = type.Type.Name; + if (treatAsSafeArgument(entry, varName, csuName)) + entry.addSafeArgument(index); + } + } + } + + // Points in the body which are reachable if we are not on the main thread. + var nonMainThreadPoints = []; + nonMainThreadPoints[body.Index[0]] = true; + + for (var edge of body.PEdge) { + // Ignore code that only executes on the main thread. + if (!(edge.Index[0] in nonMainThreadPoints)) + continue; + + var location = get_location(body.PPoint[edge.Index[0] - 1].Location); + + var callees = getCallees(edge); + for (var callee of callees) { + switch (callee.kind) { + case "direct": + var safeArguments = getEdgeSafeArguments(entry, edge, callee.name); + addCallee(new CallSite(callee.name, safeArguments, location, {})); + break; + case "resolved-field": + break; + case "field": + var field = callee.csu + "." + callee.field; + if (callee.isVirtual) + checkOverridableVirtualCall(entry, location, field); + else + checkIndirectCall(entry, location, field); + break; + case "indirect": + checkIndirectCall(entry, location, callee.variable); + break; + default: + dumpError(entry, location, "Unknown call " + callee.kind); + break; + } + } + + var fallthrough = true; + + if (edge.Kind == "Assign") { + assert(edge.Exp.length == 2); + processAssign(body, entry, location, edge.Exp[0], edge); + } else if (edge.Kind == "Call") { + assert(edge.Exp.length <= 2); + if (edge.Exp.length == 2) + processAssign(body, entry, location, edge.Exp[1], edge); + + // Treat assertion failures as if they don't return, so that + // asserting NS_IsMainThread() is sufficient to prevent the + // analysis from considering a block of code. + if (isDirectCall(edge, /MOZ_ReportAssertionFailure/)) + fallthrough = false; + } else if (edge.Kind == "Loop") { + reachableLoops[edge.BlockId.Loop] = true; + } else if (edge.Kind == "Assume") { + if (testFailsOffMainThread(edge.Exp[0], edge.PEdgeAssumeNonZero)) + fallthrough = false; + } + + if (fallthrough) + nonMainThreadPoints[edge.Index[1]] = true; + } +} + +function maybeProcessMissingFunction(entry, addCallee) +{ + // If a function is missing it might be because a destructor Foo::~Foo() is + // being called but GCC only gave us an implementation for + // Foo::~Foo(int32). See computeCallgraph.js for a little more info. + var name = entry.name; + if (name.indexOf("::~") > 0 && name.indexOf("()") > 0) { + var callee = name.replace("()", "(int32)"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + // Similarly, a call to a C1 constructor might invoke the C4 constructor. A + // mangled constructor will be something like _ZN<length><name>C1E... or in + // the case of a templatized constructor, _ZN<length><name>C1I...EE... so + // we hack it and look for "C1E" or "C1I" and replace them with their C4 + // variants. This will have rare false matches, but so far we haven't hit + // any external function calls of that sort. + if (entry.mangledName().includes("C1E") || entry.mangledName().includes("C1I")) { + var callee = name.replace("C1E", "C4E").replace("C1I", "C4I"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + // Hack to manually follow some typedefs that show up on some functions. + // This is a bug in the sixgill GCC plugin I think, since sixgill is + // supposed to follow any typedefs itself. + if (/mozilla::dom::Element/.test(name)) { + var callee = name.replace("mozilla::dom::Element", "Document::Element"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + // Hack for contravariant return types. When overriding a virtual method + // with a method that returns a different return type (a subtype of the + // original return type), we are getting the right mangled name but the + // wrong return type in the unmangled name. + if (/\$nsTextFrame*/.test(name)) { + var callee = name.replace("nsTextFrame", "nsIFrame"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + return false; +} + +function processRoot(name) +{ + var safeArguments = []; + var parameterNames = {}; + var worklist = [new WorklistEntry(name, safeArguments, [new CallSite(name, safeArguments, null, parameterNames)], parameterNames)]; + + reachable = {}; + + while (worklist.length > 0) { + var entry = worklist.pop(); + + // In principle we would be better off doing a meet-over-paths here to get + // the common subset of arguments which are safe to write through. However, + // analyzing functions separately for each subset if simpler, ensures that + // the stack traces we produce accurately characterize the stack arguments, + // and should be fast enough for now. + + if (entry.mangledName() in reachable) + continue; + reachable[entry.mangledName()] = true; + + if (ignoreContents(entry)) + continue; + + var data = xdb.read_entry(entry.name); + var dataString = data.readString(); + var callees = []; + if (dataString.length) { + // Reverse the order of the bodies we process so that we visit the + // outer function and see its assignments before the inner loops. + assignments = {}; + reachableLoops = {}; + var bodies = JSON.parse(dataString).reverse(); + for (var body of bodies) { + if (!body.BlockId.Loop || body.BlockId.Loop in reachableLoops) { + currentBody = body; + process(entry, body, Array.prototype.push.bind(callees)); + } + } + } else { + if (!maybeProcessMissingFunction(entry, Array.prototype.push.bind(callees))) + checkExternalFunction(entry); + } + xdb.free_string(data); + + for (var callee of callees) { + if (!ignoreCallEdge(entry, callee.callee)) { + var nstack = [callee, ...entry.stack]; + worklist.push(new WorklistEntry(callee.callee, callee.safeArguments, nstack, callee.parameterNames)); + } + } + } +} + +function isEdgeSafeArgument(entry, exp) +{ + var fields; + [exp, fields] = stripFields(exp); + + if (exp.Kind == "Var" && isLocalVariable(exp.Variable)) + return true; + if (exp.Kind == "Drf" && exp.Exp[0].Kind == "Var") { + var variable = exp.Exp[0].Variable; + return isSafeVariable(entry, variable); + } + if (isZero(exp)) + return true; + return false; +} + +function getEdgeSafeArguments(entry, edge, callee) +{ + assert(edge.Kind == "Call"); + var res = []; + if ("PEdgeCallInstance" in edge) { + if (isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + res.push(0); + } + if ("PEdgeCallArguments" in edge) { + var args = edge.PEdgeCallArguments.Exp; + for (var i = 0; i < args.length; i++) { + if (isEdgeSafeArgument(entry, args[i])) + res.push(i + 1); + } + } + return res; +} + +function singleAssignment(name) +{ + if (name in assignments) { + var edges = assignments[name]; + if (edges.length == 1) + return edges[0]; + } + return null; +} + +function expressionValueEdge(exp) { + if (!(exp.Kind == "Var" && exp.Variable.Kind == "Temp")) + return null; + const assign = singleAssignment(variableName(exp.Variable)); + if (!assign) + return null; + const [body, edge] = assign; + return edge; +} + +// Examples: +// +// void foo(type* aSafe) { +// type* safeBecauseNew = new type(...); +// type* unsafeBecauseMultipleAssignments = new type(...); +// if (rand()) +// unsafeBecauseMultipleAssignments = bar(); +// type* safeBecauseSingleAssignmentOfSafe = aSafe; +// } +// +function isSafeVariable(entry, variable) +{ + var index = safeArgumentIndex(variable); + if (index >= 0) + return entry.isSafeArgument(index); + + if (variable.Kind != "Temp" && variable.Kind != "Local") + return false; + var name = variableName(variable); + + if (!entry.safeLocals) + entry.safeLocals = new Map; + if (entry.safeLocals.has(name)) + return entry.safeLocals.get(name); + + const safe = isSafeLocalVariable(entry, name); + entry.safeLocals.set(name, safe); + return safe; +} + +function isSafeLocalVariable(entry, name) +{ + // If there is a single place where this variable has been assigned on + // edges we are considering, look at that edge. + var assign = singleAssignment(name); + if (assign) { + const [body, edge] = assign; + + // Treat temporary pointers to DebugOnly contents as thread local. + if (isDirectCall(edge, /DebugOnly.*?::operator/)) + return true; + + // Treat heap allocated pointers as thread local during construction. + // Hopefully the construction code doesn't leak pointers to the object + // to places where other threads might access it. + if (isDirectCall(edge, /operator new/) || + isDirectCall(edge, /nsCSSValue::Array::Create/)) + { + return true; + } + + if ("PEdgeCallInstance" in edge) { + // References to the contents of an array are threadsafe if the array + // itself is threadsafe. + if ((isDirectCall(edge, /operator\[\]/) || + isDirectCall(edge, /nsTArray.*?::InsertElementAt\b/) || + isDirectCall(edge, /nsStyleContent::ContentAt/) || + isDirectCall(edge, /nsTArray_base.*?::GetAutoArrayBuffer\b/)) && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + { + return true; + } + + // Watch for the coerced result of a getter_AddRefs or getter_Copies call. + if (isDirectCall(edge, /operator /)) { + var otherEdge = expressionValueEdge(edge.PEdgeCallInstance.Exp); + if (otherEdge && + isDirectCall(otherEdge, /getter_(?:AddRefs|Copies)/) && + isEdgeSafeArgument(entry, otherEdge.PEdgeCallArguments.Exp[0])) + { + return true; + } + } + + // RefPtr::operator->() and operator* transmit the safety of the + // RefPtr to the return value. + if (isDirectCall(edge, /RefPtr<.*?>::operator(->|\*)\(\)/) && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + { + return true; + } + + // Placement-new returns a pointer that is as safe as the pointer + // passed to it. Exp[0] is the size, Exp[1] is the pointer/address. + // Note that the invocation of the constructor is a separate call, + // and so need not be considered here. + if (isDirectCall(edge, /operator new/) && + edge.PEdgeCallInstance.Exp.length == 2 && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp[1])) + { + return true; + } + + // Coercion via AsAString preserves safety. + if (isDirectCall(edge, /AsAString/) && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + { + return true; + } + + // Special case: + // + // keyframe->mTimingFunction.emplace() + // keyframe->mTimingFunction->Init() + // + // The object calling Init should be considered safe here because + // we just emplaced it, though in general keyframe::operator-> + // could do something crazy. + if (isDirectCall(edge, /operator->/)) do { + const predges = getPredecessors(body)[edge.Index[0]]; + if (!predges || predges.length != 1) + break; + const predge = predges[0]; + if (!isDirectCall(predge, /\bemplace\b/)) + break; + const instance = predge.PEdgeCallInstance; + if (JSON.stringify(instance) == JSON.stringify(edge.PEdgeCallInstance)) + return true; + } while (false); + } + + if (isSafeAssignment(entry, edge, name)) + return true; + + // Watch out for variables which were assigned arguments. + var rhsVariable = variableAssignRhs(edge); + if (rhsVariable) + return isSafeVariable(entry, rhsVariable); + } + + // When temporary stack structures are created (either to return or to call + // methods on without assigning them a name), the generated sixgill JSON is + // rather strange. The temporary has structure type and is never assigned + // to, but is dereferenced. GCC is probably not showing us everything it is + // doing to compile this code. Pattern match for this case here. + + // The variable should have structure type. + var type = null; + for (var defvar of currentBody.DefineVariable) { + if (variableName(defvar.Variable) == name) { + type = defvar.Type; + break; + } + } + if (!type || type.Kind != "CSU") + return false; + + // The variable should not have been written to anywhere up to this point. + // If it is initialized at this point we should have seen *some* write + // already, since the CFG edges are visited in reverse post order. + if (name in assignments) + return false; + + return true; +} + +function isSafeMemberPointer(containerType, memberName, memberType) +{ + // nsTArray owns its header. + if (containerType.includes("nsTArray_base") && memberName == "mHdr") + return true; + + if (memberType.Kind != 'Pointer') + return false; + + // Special-cases go here :) + return false; +} + +// Return whether 'exp == value' holds only when execution is on the main thread. +function testFailsOffMainThread(exp, value) { + switch (exp.Kind) { + case "Drf": + var edge = expressionValueEdge(exp.Exp[0]); + if (edge) { + if (isDirectCall(edge, /NS_IsMainThread/) && value) + return true; + if (isDirectCall(edge, /IsInServoTraversal/) && !value) + return true; + if (isDirectCall(edge, /IsCurrentThreadInServoTraversal/) && !value) + return true; + if (isDirectCall(edge, /__builtin_expect/)) + return testFailsOffMainThread(edge.PEdgeCallArguments.Exp[0], value); + if (edge.Kind == "Assign") + return testFailsOffMainThread(edge.Exp[1], value); + } + break; + case "Unop": + if (exp.OpCode == "LogicalNot") + return testFailsOffMainThread(exp.Exp[0], !value); + break; + case "Binop": + if (exp.OpCode == "NotEqual" || exp.OpCode == "Equal") { + var cmpExp = isZero(exp.Exp[0]) + ? exp.Exp[1] + : (isZero(exp.Exp[1]) ? exp.Exp[0] : null); + if (cmpExp) + return testFailsOffMainThread(cmpExp, exp.OpCode == "NotEqual" ? value : !value); + } + break; + case "Int": + if (exp.String == "0" && value) + return true; + if (exp.String == "1" && !value) + return true; + break; + } + return false; +} diff --git a/js/src/devtools/rootAnalysis/analyzeRoots.js b/js/src/devtools/rootAnalysis/analyzeRoots.js new file mode 100644 index 0000000000..6e16d0cf50 --- /dev/null +++ b/js/src/devtools/rootAnalysis/analyzeRoots.js @@ -0,0 +1,1166 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +loadRelativeToScript('utility.js'); +loadRelativeToScript('annotations.js'); +loadRelativeToScript('CFG.js'); +loadRelativeToScript('dumpCFG.js'); + +var sourceRoot = (os.getenv('SOURCE') || '') + '/' + +var functionName; +var functionBodies; + +if (typeof scriptArgs[0] != 'string' || typeof scriptArgs[1] != 'string') + throw "Usage: analyzeRoots.js [-f function_name] <gcFunctions.lst> <gcEdges.txt> <limitedFunctions.lst> <gcTypes.txt> <typeInfo.txt> [start end [tmpfile]]"; + +var theFunctionNameToFind; +if (scriptArgs[0] == '--function' || scriptArgs[0] == '-f') { + theFunctionNameToFind = scriptArgs[1]; + scriptArgs = scriptArgs.slice(2); +} + +var gcFunctionsFile = scriptArgs[0] || "gcFunctions.lst"; +var gcEdgesFile = scriptArgs[1] || "gcEdges.txt"; +var limitedFunctionsFile = scriptArgs[2] || "limitedFunctions.lst"; +var gcTypesFile = scriptArgs[3] || "gcTypes.txt"; +var typeInfoFile = scriptArgs[4] || "typeInfo.txt"; +var batch = (scriptArgs[5]|0) || 1; +var numBatches = (scriptArgs[6]|0) || 1; +var tmpfile = scriptArgs[7] || "tmp.txt"; + +var gcFunctions = {}; +var text = snarf("gcFunctions.lst").split("\n"); +assert(text.pop().length == 0); +for (var line of text) + gcFunctions[mangled(line)] = true; + +var limitedFunctions = {}; +var text = snarf(limitedFunctionsFile).split("\n"); +assert(text.pop().length == 0); +for (var line of text) { + const [_, limits, func] = line.match(/(.*?) (.*)/); + assert(limits !== undefined); + limitedFunctions[func] = limits | 0; +} +text = null; + +var typeInfo = loadTypeInfo(typeInfoFile); + +var gcEdges = {}; +text = snarf(gcEdgesFile).split('\n'); +assert(text.pop().length == 0); +for (var line of text) { + var [ block, edge, func ] = line.split(" || "); + if (!(block in gcEdges)) + gcEdges[block] = {} + gcEdges[block][edge] = func; +} +text = null; + +var match; +var gcThings = {}; +var gcPointers = {}; + +text = snarf(gcTypesFile).split("\n"); +for (var line of text) { + if (match = /^GCThing: (.*)/.exec(line)) + gcThings[match[1]] = true; + if (match = /^GCPointer: (.*)/.exec(line)) + gcPointers[match[1]] = true; +} +text = null; + +function isGCType(type) +{ + if (type.Kind == "CSU") + return type.Name in gcThings; + else if (type.Kind == "Array") + return isGCType(type.Type); + return false; +} + +function isUnrootedType(type) +{ + if (type.Kind == "Pointer") + return isGCType(type.Type); + else if (type.Kind == "Array") { + if (!type.Type) { + printErr("Received Array Kind with no Type"); + printErr(JSON.stringify(type)); + printErr(getBacktrace({args: true, locals: true})); + } + return isUnrootedType(type.Type); + } else if (type.Kind == "CSU") + return type.Name in gcPointers; + else + return false; +} + +function expressionUsesVariable(exp, variable) +{ + if (exp.Kind == "Var" && sameVariable(exp.Variable, variable)) + return true; + if (!("Exp" in exp)) + return false; + for (var childExp of exp.Exp) { + if (expressionUsesVariable(childExp, variable)) + return true; + } + return false; +} + +function expressionUsesVariableContents(exp, variable) +{ + if (!("Exp" in exp)) + return false; + for (var childExp of exp.Exp) { + if (childExp.Kind == 'Drf') { + if (expressionUsesVariable(childExp, variable)) + return true; + } else if (expressionUsesVariableContents(childExp, variable)) { + return true; + } + } + return false; +} + +function isImmobileValue(exp) { + if (exp.Kind == "Int" && exp.String == "0") { + return true; + } + return false; +} + +// Detect simple |return nullptr;| statements. +function isReturningImmobileValue(edge, variable) +{ + if (variable.Kind == "Return") { + if (edge.Exp[0].Kind == "Var" && sameVariable(edge.Exp[0].Variable, variable)) { + if (isImmobileValue(edge.Exp[1])) + return true; + } + } + return false; +} + +// If the edge uses the given variable's value, return the earliest point at +// which the use is definite. Usually, that means the source of the edge +// (anything that reaches that source point will end up using the variable, but +// there may be other ways to reach the destination of the edge.) +// +// Return values are implicitly used at the very last point in the function. +// This makes a difference: if an RAII class GCs in its destructor, we need to +// start looking at the final point in the function, not one point back from +// that, since that would skip over the GCing call. +// +// Note that this returns true only if the variable's incoming value is used. +// So this would return false for 'obj': +// +// obj = someFunction(); +// +// but these would return true: +// +// obj = someFunction(obj); +// obj->foo = someFunction(); +// +function edgeUsesVariable(edge, variable, body) +{ + if (ignoreEdgeUse(edge, variable, body)) + return 0; + + if (variable.Kind == "Return" && body.Index[1] == edge.Index[1] && body.BlockId.Kind == "Function") + return edge.Index[1]; // Last point in function body uses the return value. + + var src = edge.Index[0]; + + switch (edge.Kind) { + + case "Assign": { + // Detect `Return := nullptr`. + if (isReturningImmobileValue(edge, variable)) + return 0; + const [lhs, rhs] = edge.Exp; + // Detect `lhs := ...variable...` + if (expressionUsesVariable(rhs, variable)) + return src; + // Detect `...variable... := rhs` but not `variable := rhs`. The latter + // overwrites the previous value of `variable` without using it. + if (expressionUsesVariable(lhs, variable) && !expressionIsVariable(lhs, variable)) + return src; + return 0; + } + + case "Assume": + return expressionUsesVariableContents(edge.Exp[0], variable) ? src : 0; + + case "Call": { + const callee = edge.Exp[0]; + if (expressionUsesVariable(callee, variable)) + return src; + if ("PEdgeCallInstance" in edge) { + if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable)) { + if (edgeKillsVariable(edge, variable)) { + // If the variable is being constructed, then the incoming + // value is not used here; it didn't exist before + // construction. (The analysis doesn't get told where + // variables are defined, so must infer it from + // construction. If the variable does not have a + // constructor, its live range may be larger than it really + // ought to be if it is defined within a loop body, but + // that is conservative.) + } else { + return src; + } + } + } + if ("PEdgeCallArguments" in edge) { + for (var exp of edge.PEdgeCallArguments.Exp) { + if (expressionUsesVariable(exp, variable)) + return src; + } + } + if (edge.Exp.length == 1) + return 0; + + // Assigning call result to a variable. + const lhs = edge.Exp[1]; + if (expressionUsesVariable(lhs, variable) && !expressionIsVariable(lhs, variable)) + return src; + return 0; + } + + case "Loop": + return 0; + + case "Assembly": + return 0; + + default: + assert(false); + } +} + +function expressionIsVariableAddress(exp, variable) +{ + while (exp.Kind == "Fld") + exp = exp.Exp[0]; + return exp.Kind == "Var" && sameVariable(exp.Variable, variable); +} + +function edgeTakesVariableAddress(edge, variable, body) +{ + if (ignoreEdgeUse(edge, variable, body)) + return false; + if (ignoreEdgeAddressTaken(edge)) + return false; + switch (edge.Kind) { + case "Assign": + return expressionIsVariableAddress(edge.Exp[1], variable); + case "Call": + if ("PEdgeCallArguments" in edge) { + for (var exp of edge.PEdgeCallArguments.Exp) { + if (expressionIsVariableAddress(exp, variable)) + return true; + } + } + return false; + default: + return false; + } +} + +function expressionIsVariable(exp, variable) +{ + return exp.Kind == "Var" && sameVariable(exp.Variable, variable); +} + +function expressionIsMethodOnVariable(exp, variable) +{ + // This might be calling a method on a base class, in which case exp will + // be an unnamed field of the variable instead of the variable itself. + while (exp.Kind == "Fld" && exp.Field.Name[0].startsWith("field:")) + exp = exp.Exp[0]; + + return exp.Kind == "Var" && sameVariable(exp.Variable, variable); +} + +// Return whether the edge terminates the live range of a variable's value when +// searching in reverse through the CFG, by setting it to some new value. +// Examples of killing 'obj's live range: +// +// obj = foo; +// obj = foo(); +// obj = foo(obj); // uses previous value but then sets to new value +// SomeClass obj(true, 1); // constructor +// +function edgeKillsVariable(edge, variable) +{ + // Direct assignments kill their lhs: var = value + if (edge.Kind == "Assign") { + const [lhs, rhs] = edge.Exp; + return (expressionIsVariable(lhs, variable) && + !isReturningImmobileValue(edge, variable)); + } + + if (edge.Kind != "Call") + return false; + + // Assignments of call results kill their lhs. + if (1 in edge.Exp) { + var lhs = edge.Exp[1]; + if (expressionIsVariable(lhs, variable)) + return true; + } + + // Constructor calls kill their 'this' value. + if ("PEdgeCallInstance" in edge) { + var instance = edge.PEdgeCallInstance.Exp; + + // Kludge around incorrect dereference on some constructor calls. + if (instance.Kind == "Drf") + instance = instance.Exp[0]; + + if (!expressionIsVariable(instance, variable)) + return false; + + var callee = edge.Exp[0]; + if (callee.Kind != "Var") + return false; + + assert(callee.Variable.Kind == "Func"); + var calleeName = readable(callee.Variable.Name[0]); + + // Constructor calls include the text 'Name::Name(' or 'Name<...>::Name('. + var openParen = calleeName.indexOf('('); + if (openParen < 0) + return false; + calleeName = calleeName.substring(0, openParen); + + var lastColon = calleeName.lastIndexOf('::'); + if (lastColon < 0) + return false; + var constructorName = calleeName.substr(lastColon + 2); + calleeName = calleeName.substr(0, lastColon); + + var lastTemplateOpen = calleeName.lastIndexOf('<'); + if (lastTemplateOpen >= 0) + calleeName = calleeName.substr(0, lastTemplateOpen); + + if (calleeName.endsWith(constructorName)) + return true; + } + + return false; +} + +function edgeMovesVariable(edge, variable) +{ + if (edge.Kind != 'Call') + return false; + const callee = edge.Exp[0]; + if (callee.Kind == 'Var' && + callee.Variable.Kind == 'Func') + { + const { Variable: { Name: [ fullname, shortname ] } } = callee; + const [ mangled, unmangled ] = splitFunction(fullname); + // Match a UniquePtr move constructor. + if (unmangled.match(/::UniquePtr<[^>]*>::UniquePtr\((\w+::)*UniquePtr<[^>]*>&&/)) + return true; + } + + return false; +} + +// Scan forward through the given 'body', starting at 'startpoint', looking for +// a call that passes 'variable' to a move constructor that "consumes" it (eg +// UniquePtr::UniquePtr(UniquePtr&&)). +function bodyEatsVariable(variable, body, startpoint) +{ + const successors = getSuccessors(body); + const work = [startpoint]; + while (work.length > 0) { + const point = work.shift(); + if (!(point in successors)) + continue; + for (const edge of successors[point]) { + if (edgeMovesVariable(edge, variable)) + return true; + // edgeKillsVariable will find places where 'variable' is given a + // new value. Never observed in practice, since this function is + // only called with a temporary resulting from std::move(), which + // is used immediately for a call. But just to be robust to future + // uses: + if (!edgeKillsVariable(edge, variable)) + work.push(edge.Index[1]); + } + } + return false; +} + +// Return whether an edge "clears out" a variable's value. A simple example +// would be +// +// var = nullptr; +// +// for analyses for which nullptr is a "safe" value (eg GC rooting hazards; you +// can't get in trouble by holding a nullptr live across a GC.) A more complex +// example is a Maybe<T> that gets reset: +// +// Maybe<AutoCheckCannotGC> nogc; +// nogc.emplace(cx); +// nogc.reset(); +// gc(); // <-- not a problem; nogc is invalidated by prev line +// nogc.emplace(cx); +// foo(nogc); +// +// Yet another example is a UniquePtr being passed by value, which means the +// receiver takes ownership: +// +// UniquePtr<JSObject*> uobj(obj); +// foo(uobj); +// gc(); +// +// Compare to edgeKillsVariable: killing (in backwards direction) means the +// variable's value was live and is no longer. Invalidating means it wasn't +// actually live after all. +// +function edgeInvalidatesVariable(edge, variable, body) +{ + // var = nullptr; + if (edge.Kind == "Assign") { + const [lhs, rhs] = edge.Exp; + return expressionIsVariable(lhs, variable) && isImmobileValue(rhs); + } + + if (edge.Kind != "Call") + return false; + + var callee = edge.Exp[0]; + + if (edge.Type.Kind == 'Function' && + edge.Exp[0].Kind == 'Var' && + edge.Exp[0].Variable.Kind == 'Func' && + edge.Exp[0].Variable.Name[1] == 'move' && + edge.Exp[0].Variable.Name[0].includes('std::move(') && + expressionIsVariable(edge.PEdgeCallArguments.Exp[0], variable) && + edge.Exp[1].Kind == 'Var' && + edge.Exp[1].Variable.Kind == 'Temp') + { + // temp = std::move(var) + // + // If var is a UniquePtr, and we pass it into something that takes + // ownership, then it should be considered to be invalid. It really + // ought to be invalidated at the point of the function call that calls + // the move constructor, but given that we're creating a temporary here + // just for the purpose of passing it in, this edge is good enough. + const lhs = edge.Exp[1].Variable; + if (bodyEatsVariable(lhs, body, edge.Index[1])) + return true; + } + + if (edge.Type.Kind == 'Function' && + edge.Type.TypeFunctionCSU && + edge.PEdgeCallInstance && + expressionIsMethodOnVariable(edge.PEdgeCallInstance.Exp, variable)) + { + const typeName = edge.Type.TypeFunctionCSU.Type.Name; + const m = typeName.match(/^(((\w|::)+?)(\w+))</); + if (m) { + const [, type, namespace,, classname] = m; + + // special-case: the initial constructor that doesn't provide a value. + // Useful for things like Maybe<T>. + const ctorName = `${namespace}${classname}<T>::${classname}()`; + if (callee.Kind == 'Var' && + typesWithSafeConstructors.has(type) && + callee.Variable.Name[0].includes(ctorName)) + { + return true; + } + + // special-case: UniquePtr::reset() and similar. + if (callee.Kind == 'Var' && + type in resetterMethods && + resetterMethods[type].has(callee.Variable.Name[1])) + { + return true; + } + } + } + + // special-case: passing UniquePtr<T> by value. + if (edge.Type.Kind == 'Function' && + edge.Type.TypeFunctionArgument && + edge.PEdgeCallArguments) + { + for (const i in edge.Type.TypeFunctionArgument) { + const param = edge.Type.TypeFunctionArgument[i]; + if (param.Type.Kind != 'CSU') + continue; + if (!param.Type.Name.startsWith("mozilla::UniquePtr<")) + continue; + const arg = edge.PEdgeCallArguments.Exp[i]; + if (expressionIsVariable(arg, variable)) { + return true; + } + } + } + + return false; +} + +function edgeCanGC(edge) +{ + if (edge.Kind != "Call") + return false; + + var callee = edge.Exp[0]; + + while (callee.Kind == "Drf") + callee = callee.Exp[0]; + + if (callee.Kind == "Var") { + var variable = callee.Variable; + + if (variable.Kind == "Func") { + var func = mangled(variable.Name[0]); + if ((func in gcFunctions) || ((func + internalMarker) in gcFunctions)) + return "'" + variable.Name[0] + "'"; + return null; + } + + var varName = variable.Name[0]; + return indirectCallCannotGC(functionName, varName) ? null : "'*" + varName + "'"; + } + + if (callee.Kind == "Fld") { + var field = callee.Field; + var csuName = field.FieldCSU.Type.Name; + var fullFieldName = csuName + "." + field.Name[0]; + if (fieldCallCannotGC(csuName, fullFieldName)) + return null; + + if (fullFieldName in gcFunctions) + return "'" + fullFieldName + "'"; + + return null; + } +} + +// Search recursively through predecessors from the use of a variable's value, +// returning whether a GC call is reachable (in the reverse direction; this +// means that the variable use is reachable from the GC call, and therefore the +// variable is live after the GC call), along with some additional information. +// What info we want depends on whether the variable turns out to be live +// across a GC call. We are looking for both hazards (unrooted variables live +// across GC calls) and unnecessary roots (rooted variables that have no GC +// calls in their live ranges.) +// +// If not: +// +// - 'minimumUse': the earliest point in each body that uses the variable, for +// reporting on unnecessary roots. +// +// If so: +// +// - 'why': a path from the GC call to a use of the variable after the GC +// call, chained through a 'why' field in the returned edge descriptor +// +// - 'gcInfo': a direct pointer to the GC call edge +// +function findGCBeforeValueUse(start_body, start_point, suppressed, variable) +{ + // Scan through all edges preceding an unrooted variable use, using an + // explicit worklist, looking for a GC call. A worklist contains an + // incoming edge together with a description of where it or one of its + // successors GC'd (if any). + + var bodies_visited = new Map(); + + let worklist = [{body: start_body, ppoint: start_point, preGCLive: false, gcInfo: null, why: null}]; + while (worklist.length) { + // Grab an entry off of the worklist, representing a point within the + // CFG identified by <body,ppoint>. If this point has a descendant + // later in the CFG that can GC, gcInfo will be set to the information + // about that GC call. + + var entry = worklist.pop(); + var { body, ppoint, gcInfo, preGCLive } = entry; + + // Handle the case where there are multiple ways to reach this point + // (traversing backwards). + var visited = bodies_visited.get(body); + if (!visited) + bodies_visited.set(body, visited = new Map()); + if (visited.has(ppoint)) { + var seenEntry = visited.get(ppoint); + + // This point already knows how to GC through some other path, so + // we have nothing new to learn. (The other path will consider the + // predecessors.) + if (seenEntry.gcInfo) + continue; + + // If this worklist's entry doesn't know of any way to GC, then + // there's no point in continuing the traversal through it. Perhaps + // another edge will be found that *can* GC; otherwise, the first + // route to the point will traverse through predecessors. + // + // Note that this means we may visit a point more than once, if the + // first time we visit we don't have a known reachable GC call and + // the second time we do. + if (!gcInfo) + continue; + } + visited.set(ppoint, {body: body, gcInfo: gcInfo}); + + // Check for hitting the entry point of the current body (which may be + // the outer function or a loop within it.) + if (ppoint == body.Index[0]) { + if (body.BlockId.Kind == "Loop") { + // Propagate to outer body parents that enter the loop body. + if ("BlockPPoint" in body) { + for (var parent of body.BlockPPoint) { + var found = false; + for (var xbody of functionBodies) { + if (sameBlockId(xbody.BlockId, parent.BlockId)) { + assert(!found); + found = true; + worklist.push({body: xbody, ppoint: parent.Index, + gcInfo: gcInfo, why: entry}); + } + } + assert(found); + } + } + + // Also propagate to the *end* of this loop, for the previous + // iteration. + worklist.push({body: body, ppoint: body.Index[1], + gcInfo: gcInfo, why: entry}); + } else if ((variable.Kind == "Arg" || variable.Kind == "This") && gcInfo) { + // The scope of arguments starts at the beginning of the + // function + return entry; + } else if (entry.preGCLive) { + // We didn't find a "good" explanation beginning of the live + // range, but we do know the variable was live across the GC. + // This can happen if the live range started when a variable is + // used as a retparam. + return entry; + } + } + + var predecessors = getPredecessors(body); + if (!(ppoint in predecessors)) + continue; + + for (var edge of predecessors[ppoint]) { + var source = edge.Index[0]; + + if (edgeInvalidatesVariable(edge, variable, body)) { + // Terminate the search through this point; we thought we were + // within the live range, but it turns out that the variable + // was set to a value that we don't care about. + continue; + } + + var edge_kills = edgeKillsVariable(edge, variable); + var edge_uses = edgeUsesVariable(edge, variable, body); + + if (edge_kills || edge_uses) { + if (!body.minimumUse || source < body.minimumUse) + body.minimumUse = source; + } + + if (edge_kills) { + // This is a beginning of the variable's live range. If we can + // reach a GC call from here, then we're done -- we have a path + // from the beginning of the live range, through the GC call, + // to a use after the GC call that proves its live range + // extends at least that far. + if (gcInfo) + return {body: body, ppoint: source, gcInfo: gcInfo, why: entry }; + + // Otherwise, keep searching through the graph, but truncate + // this particular branch of the search at this edge. + continue; + } + + var src_gcInfo = gcInfo; + var src_preGCLive = preGCLive; + if (!gcInfo && !(body.limits[source] & LIMIT_CANNOT_GC) && !suppressed) { + var gcName = edgeCanGC(edge, body); + if (gcName) + src_gcInfo = {name:gcName, body:body, ppoint:source}; + } + + if (edge_uses) { + // The live range starts at least this far back, so we're done + // for the same reason as with edge_kills. The only difference + // is that a GC on this edge indicates a hazard, whereas if + // we're killing a live range in the GC call then it's not live + // *across* the call. + // + // However, we may want to generate a longer usage chain for + // the variable than is minimally necessary. For example, + // consider: + // + // Value v = f(); + // if (v.isUndefined()) + // return false; + // gc(); + // return v; + // + // The call to .isUndefined() is considered to be a use and + // therefore indicates that v must be live at that point. But + // it's more helpful to the user to continue the 'why' path to + // include the ancestor where the value was generated. So we + // will only return here if edge.Kind is Assign; otherwise, + // we'll pass a "preGCLive" value up through the worklist to + // remember that the variable *is* alive before the GC and so + // this function should be returning a true value even if we + // don't find an assignment. + + if (src_gcInfo) { + src_preGCLive = true; + if (edge.Kind == 'Assign') + return {body:body, ppoint:source, gcInfo:src_gcInfo, why:entry}; + } + } + + if (edge.Kind == "Loop") { + // Additionally propagate the search into a loop body, starting + // with the exit point. + var found = false; + for (var xbody of functionBodies) { + if (sameBlockId(xbody.BlockId, edge.BlockId)) { + assert(!found); + found = true; + worklist.push({body:xbody, ppoint:xbody.Index[1], + preGCLive: src_preGCLive, gcInfo:src_gcInfo, + why:entry}); + } + } + assert(found); + // Don't continue to predecessors here without going through + // the loop. (The points in this body that enter the loop will + // be traversed when we reach the entry point of the loop.) + break; + } + + // Propagate the search to the predecessors of this edge. + worklist.push({body:body, ppoint:source, + preGCLive: src_preGCLive, gcInfo:src_gcInfo, + why:entry}); + } + } + + return null; +} + +function variableLiveAcrossGC(suppressed, variable) +{ + // A variable is live across a GC if (1) it is used by an edge (as in, it + // was at least initialized), and (2) it is used after a GC in a successor + // edge. + + for (var body of functionBodies) + body.minimumUse = 0; + + for (var body of functionBodies) { + if (!("PEdge" in body)) + continue; + for (var edge of body.PEdge) { + // Examples: + // + // JSObject* obj = NewObject(); + // cangc(); + // obj = NewObject(); <-- mentions 'obj' but kills previous value + // + // This is not a hazard. Contrast this with: + // + // JSObject* obj = NewObject(); + // cangc(); + // obj = LookAt(obj); <-- uses 'obj' and kills previous value + // + // This is a hazard; the initial value of obj is live across + // cangc(). And a third possibility: + // + // JSObject* obj = NewObject(); + // obj = CopyObject(obj); + // + // This is not a hazard, because even though CopyObject can GC, obj + // is not live across it. (obj is live before CopyObject, and + // probably after, but not across.) There may be a hazard within + // CopyObject, of course. + // + + // Ignore uses that are just invalidating the previous value. + if (edgeInvalidatesVariable(edge, variable, body)) + continue; + + var usePoint = edgeUsesVariable(edge, variable, body); + if (usePoint) { + var call = findGCBeforeValueUse(body, usePoint, suppressed, variable); + if (!call) + continue; + + call.afterGCUse = usePoint; + return call; + } + } + } + return null; +} + +// An unrooted variable has its address stored in another variable via +// assignment, or passed into a function that can GC. If the address is +// assigned into some other variable, we can't track it to see if it is held +// live across a GC. If it is passed into a function that can GC, then it's +// sort of like a Handle to an unrooted location, and the callee could GC +// before overwriting it or rooting it. +function unsafeVariableAddressTaken(suppressed, variable) +{ + for (var body of functionBodies) { + if (!("PEdge" in body)) + continue; + for (var edge of body.PEdge) { + if (edgeTakesVariableAddress(edge, variable, body)) { + if (edge.Kind == "Assign" || (!suppressed && edgeCanGC(edge))) + return {body:body, ppoint:edge.Index[0]}; + } + } + } + return null; +} + +// Read out the brief (non-JSON, semi-human-readable) CFG description for the +// given function and store it. +function loadPrintedLines(functionName) +{ + assert(!os.system("xdbfind src_body.xdb '" + functionName + "' > " + tmpfile)); + var lines = snarf(tmpfile).split('\n'); + + for (var body of functionBodies) + body.lines = []; + + // Distribute lines of output to the block they originate from. + var currentBody = null; + for (var line of lines) { + if (/^block:/.test(line)) { + if (match = /:(loop#[\d#]+)/.exec(line)) { + var loop = match[1]; + var found = false; + for (var body of functionBodies) { + if (body.BlockId.Kind == "Loop" && body.BlockId.Loop == loop) { + assert(!found); + found = true; + currentBody = body; + } + } + assert(found); + } else { + for (var body of functionBodies) { + if (body.BlockId.Kind == "Function") + currentBody = body; + } + } + } + if (currentBody) + currentBody.lines.push(line); + } +} + +function findLocation(body, ppoint, opts={brief: false}) +{ + var location = body.PPoint[ppoint - 1].Location; + var file = location.CacheString; + + if (file.indexOf(sourceRoot) == 0) + file = file.substring(sourceRoot.length); + + if (opts.brief) { + var m = /.*\/(.*)/.exec(file); + if (m) + file = m[1]; + } + + return file + ":" + location.Line; +} + +function locationLine(text) +{ + if (match = /:(\d+)$/.exec(text)) + return match[1]; + return 0; +} + +function printEntryTrace(functionName, entry) +{ + var gcPoint = entry.gcInfo ? entry.gcInfo.ppoint : 0; + + if (!functionBodies[0].lines) + loadPrintedLines(functionName); + + while (entry) { + var ppoint = entry.ppoint; + var lineText = findLocation(entry.body, ppoint, {"brief": true}); + + var edgeText = ""; + if (entry.why && entry.why.body == entry.body) { + // If the next point in the trace is in the same block, look for an edge between them. + var next = entry.why.ppoint; + + if (!entry.body.edgeTable) { + var table = {}; + entry.body.edgeTable = table; + for (var line of entry.body.lines) { + if (match = /^\w+\((\d+,\d+),/.exec(line)) + table[match[1]] = line; // May be multiple? + } + if (entry.body.BlockId.Kind == 'Loop') { + const [startPoint, endPoint] = entry.body.Index; + table[`${endPoint},${startPoint}`] = '(loop to next iteration)'; + } + } + + edgeText = entry.body.edgeTable[ppoint + "," + next]; + assert(edgeText); + if (ppoint == gcPoint) + edgeText += " [[GC call]]"; + } else { + // Look for any outgoing edge from the chosen point. + for (var line of entry.body.lines) { + if (match = /\((\d+),/.exec(line)) { + if (match[1] == ppoint) { + edgeText = line; + break; + } + } + } + if (ppoint == entry.body.Index[1] && entry.body.BlockId.Kind == "Function") + edgeText += " [[end of function]]"; + } + + print(" " + lineText + (edgeText.length ? ": " + edgeText : "")); + entry = entry.why; + } +} + +function isRootedType(type) +{ + return type.Kind == "CSU" && ((type.Name in typeInfo.RootedPointers) || + (type.Name in typeInfo.RootedGCThings)); +} + +function typeDesc(type) +{ + if (type.Kind == "CSU") { + return type.Name; + } else if ('Type' in type) { + var inner = typeDesc(type.Type); + if (type.Kind == 'Pointer') + return inner + '*'; + else if (type.Kind == 'Array') + return inner + '[]'; + else + return inner + '?'; + } else { + return '???'; + } +} + +function processBodies(functionName) +{ + if (!("DefineVariable" in functionBodies[0])) + return; + var suppressed = Boolean(limitedFunctions[mangled(functionName)] & LIMIT_CANNOT_GC); + + // Look for the JS_EXPECT_HAZARDS annotation, and output a different + // message in that case that won't be counted as a hazard. + var annotations = new Set(); + for (const variable of functionBodies[0].DefineVariable) { + if (variable.Variable.Kind == "Func" && variable.Variable.Name[0] == functionName) { + for (const { Name: [tag, value] } of (variable.Type.Annotation || [])) { + if (tag == 'annotate') + annotations.add(value); + } + } + } + + var missingExpectedHazard = annotations.has("Expect Hazards"); + + // Awful special case, hopefully temporary: + // + // The DOM bindings code generator uses "holders" to externally root + // variables. So for example: + // + // StringObjectRecordOrLong arg0; + // StringObjectRecordOrLongArgument arg0_holder(arg0); + // arg0_holder.TrySetToStringObjectRecord(cx, args[0]); + // GC(); + // self->PassUnion22(cx, arg0); + // + // This appears to be a rooting hazard on arg0, but it is rooted by + // arg0_holder if you set it to any of its union types that requires + // rooting. + // + // Additionally, the holder may be reported as a hazard because it's not + // itself a Rooted or a subclass of AutoRooter; it contains a + // Maybe<RecordRooter<T>> that will get emplaced if rooting is required. + // + // Hopefully these will be simplified at some point (see bug 1517829), but + // for now we special-case functions in the mozilla::dom namespace that + // contain locals with types ending in "Argument". Or + // Maybe<SomethingArgument>. It's a harsh world. + const ignoreVars = new Set(); + if (functionName.match(/mozilla::dom::/)) { + const vars = functionBodies[0].DefineVariable.filter( + v => v.Type.Kind == 'CSU' && v.Variable.Kind == 'Local' + ).map( + v => [ v.Variable.Name[0], v.Type.Name ] + ); + + const holders = vars.filter(([n, t]) => n.match(/^arg\d+_holder$/) && t.match(/Argument\b/)); + for (const [holder,] of holders) { + ignoreVars.add(holder); // Ignore the older. + ignoreVars.add(holder.replace("_holder", "")); // Ignore the "managed" arg. + } + } + + for (const variable of functionBodies[0].DefineVariable) { + var name; + if (variable.Variable.Kind == "This") + name = "this"; + else if (variable.Variable.Kind == "Return") + name = "<returnvalue>"; + else + name = variable.Variable.Name[0]; + + if (ignoreVars.has(name)) + continue; + + if (isRootedType(variable.Type)) { + if (!variableLiveAcrossGC(suppressed, variable.Variable)) { + // The earliest use of the variable should be its constructor. + var lineText; + for (var body of functionBodies) { + if (body.minimumUse) { + var text = findLocation(body, body.minimumUse); + if (!lineText || locationLine(lineText) > locationLine(text)) + lineText = text; + } + } + print("\nFunction '" + functionName + "'" + + " has unnecessary root '" + name + "' at " + lineText); + } + } else if (isUnrootedType(variable.Type)) { + var result = variableLiveAcrossGC(suppressed, variable.Variable); + if (result) { + var lineText = findLocation(result.gcInfo.body, result.gcInfo.ppoint); + if (annotations.has('Expect Hazards')) { + print("\nThis is expected, but '" + functionName + "'" + + " has unrooted '" + name + "'" + + " of type '" + typeDesc(variable.Type) + "'" + + " live across GC call " + result.gcInfo.name + + " at " + lineText); + missingExpectedHazard = false; + } else { + print("\nFunction '" + functionName + "'" + + " has unrooted '" + name + "'" + + " of type '" + typeDesc(variable.Type) + "'" + + " live across GC call " + result.gcInfo.name + + " at " + lineText); + } + printEntryTrace(functionName, result); + } + result = unsafeVariableAddressTaken(suppressed, variable.Variable); + if (result) { + var lineText = findLocation(result.body, result.ppoint); + print("\nFunction '" + functionName + "'" + + " takes unsafe address of unrooted '" + name + "'" + + " at " + lineText); + printEntryTrace(functionName, {body:result.body, ppoint:result.ppoint}); + } + } + } + + if (missingExpectedHazard) { + const { + Location: [ + { CacheString: startfile, Line: startline }, + { CacheString: endfile, Line: endline } + ] + } = functionBodies[0]; + + const loc = (startfile == endfile) ? `${startfile}:${startline}-${endline}` + : `${startfile}:${startline}`; + + print("\nFunction '" + functionName + "' expected hazard(s) but none were found at " + loc); + } +} + +if (batch == 1) + print("Time: " + new Date); + +var xdb = xdbLibrary(); +xdb.open("src_body.xdb"); + +var minStream = xdb.min_data_stream()|0; +var maxStream = xdb.max_data_stream()|0; + +var N = (maxStream - minStream) + 1; +var start = Math.floor((batch - 1) / numBatches * N) + minStream; +var start_next = Math.floor(batch / numBatches * N) + minStream; +var end = start_next - 1; + +function process(name, json) { + functionName = name; + functionBodies = JSON.parse(json); + + // Annotate body with a table of all points within the body that may be in + // a limited scope (eg within the scope of a GC suppression RAII class.) + // body.limits is a plain object indexed by point, with the value being a + // bit set stored in an integer of the limit bits. + for (var body of functionBodies) + body.limits = []; + + for (var body of functionBodies) { + for (var [pbody, id, limits] of allRAIIGuardedCallPoints(typeInfo, functionBodies, body, isLimitConstructor)) + { + if (limits) + pbody.limits[id] = limits; + } + } + processBodies(functionName); +} + +if (theFunctionNameToFind) { + var data = xdb.read_entry(theFunctionNameToFind); + var json = data.readString(); + process(theFunctionNameToFind, json); + xdb.free_string(data); + quit(0); +} + +for (var nameIndex = start; nameIndex <= end; nameIndex++) { + var name = xdb.read_key(nameIndex); + var functionName = name.readString(); + var data = xdb.read_entry(name); + xdb.free_string(name); + var json = data.readString(); + try { + process(functionName, json); + } catch (e) { + printErr("Exception caught while handling " + functionName); + throw(e); + } + xdb.free_string(data); +} diff --git a/js/src/devtools/rootAnalysis/annotations.js b/js/src/devtools/rootAnalysis/annotations.js new file mode 100644 index 0000000000..93d022dd83 --- /dev/null +++ b/js/src/devtools/rootAnalysis/annotations.js @@ -0,0 +1,529 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +// Ignore calls made through these function pointers +var ignoreIndirectCalls = { + "mallocSizeOf" : true, + "aMallocSizeOf" : true, + "__conv" : true, + "__convf" : true, + "prerrortable.c:callback_newtable" : true, + "mozalloc_oom.cpp:void (* gAbortHandler)(size_t)" : true, +}; + +// Types that when constructed with no arguments, are "safe" values (they do +// not contain GC pointers). +var typesWithSafeConstructors = new Set([ + "mozilla::Maybe", + "mozilla::dom::Nullable", + "mozilla::dom::Optional", + "mozilla::UniquePtr", + "js::UniquePtr" +]); + +var resetterMethods = { + 'mozilla::Maybe': new Set(["reset"]), + 'mozilla::UniquePtr': new Set(["reset"]), + 'js::UniquePtr': new Set(["reset"]), + 'mozilla::dom::Nullable': new Set(["SetNull"]), + 'mozilla::dom::TypedArray_base': new Set(["Reset"]), +}; + +function indirectCallCannotGC(fullCaller, fullVariable) +{ + var caller = readable(fullCaller); + + // This is usually a simple variable name, but sometimes a full name gets + // passed through. And sometimes that name is truncated. Examples: + // _ZL13gAbortHandler|mozalloc_oom.cpp:void (* gAbortHandler)(size_t) + // _ZL14pMutexUnlockFn|umutex.cpp:void (* pMutexUnlockFn)(const void* + var name = readable(fullVariable); + + if (name in ignoreIndirectCalls) + return true; + + if (name == "mapper" && caller == "ptio.c:pt_MapError") + return true; + + if (name == "params" && caller == "PR_ExplodeTime") + return true; + + // hook called during script finalization which cannot GC. + if (/CallDestroyScriptHook/.test(caller)) + return true; + + // Call through a 'callback' function pointer, in a place where we're going + // to be throwing a JS exception. + if (name == "callback" && caller.includes("js::ErrorToException")) + return true; + + // The math cache only gets called with non-GC math functions. + if (name == "f" && caller.includes("js::MathCache::lookup")) + return true; + + // It would probably be better to somehow rewrite PR_CallOnce(foo) into a + // call of foo, but for now just assume that nobody is crazy enough to use + // PR_CallOnce with a function that can GC. + if (name == "func" && caller == "PR_CallOnce") + return true; + + return false; +} + +// Ignore calls through functions pointers with these types +var ignoreClasses = { + "JSStringFinalizer" : true, + "SprintfState" : true, + "SprintfStateStr" : true, + "JSLocaleCallbacks" : true, + "JSC::ExecutableAllocator" : true, + "PRIOMethods": true, + "_MD_IOVector" : true, + "malloc_table_t": true, // replace_malloc + "malloc_hook_table_t": true, // replace_malloc + "mozilla::MallocSizeOf": true, + "MozMallocSizeOf": true, +}; + +// Ignore calls through TYPE.FIELD, where TYPE is the class or struct name containing +// a function pointer field named FIELD. +var ignoreCallees = { + "js::Class.trace" : true, + "js::Class.finalize" : true, + "JSClassOps.trace" : true, + "JSClassOps.finalize" : true, + "JSRuntime.destroyPrincipals" : true, + "icu_50::UObject.__deleting_dtor" : true, // destructors in ICU code can't cause GC + "mozilla::CycleCollectedJSRuntime.DescribeCustomObjects" : true, // During tracing, cannot GC. + "mozilla::CycleCollectedJSRuntime.NoteCustomGCThingXPCOMChildren" : true, // During tracing, cannot GC. + "PLDHashTableOps.hashKey" : true, + "PLDHashTableOps.clearEntry" : true, + "z_stream_s.zfree" : true, + "z_stream_s.zalloc" : true, + "GrGLInterface.fCallback" : true, + "std::strstreambuf._M_alloc_fun" : true, + "std::strstreambuf._M_free_fun" : true, + "struct js::gc::Callback<void (*)(JSContext*, void*)>.op" : true, + "mozilla::ThreadSharedFloatArrayBufferList::Storage.mFree" : true, + "mozilla::SizeOfState.mMallocSizeOf": true, +}; + +function fieldCallCannotGC(csu, fullfield) +{ + if (csu in ignoreClasses) + return true; + if (fullfield in ignoreCallees) + return true; + return false; +} + +function ignoreEdgeUse(edge, variable, body) +{ + // Horrible special case for ignoring a false positive in xptcstubs: there + // is a local variable 'paramBuffer' holding an array of nsXPTCMiniVariant + // on the stack, which appears to be live across a GC call because its + // constructor is called when the array is initialized, even though the + // constructor is a no-op. So we'll do a very narrow exclusion for the use + // that incorrectly started the live range, which was basically "__temp_1 = + // paramBuffer". + // + // By scoping it so narrowly, we can detect most hazards that would be + // caused by modifications in the PrepareAndDispatch code. It just barely + // avoids having a hazard already. + if (('Name' in variable) && (variable.Name[0] == 'paramBuffer')) { + if (body.BlockId.Kind == 'Function' && body.BlockId.Variable.Name[0] == 'PrepareAndDispatch') + if (edge.Kind == 'Assign' && edge.Type.Kind == 'Pointer') + if (edge.Exp[0].Kind == 'Var' && edge.Exp[1].Kind == 'Var') + if (edge.Exp[1].Variable.Kind == 'Local' && edge.Exp[1].Variable.Name[0] == 'paramBuffer') + return true; + } + + // Functions which should not be treated as using variable. + if (edge.Kind == "Call") { + var callee = edge.Exp[0]; + if (callee.Kind == "Var") { + var name = callee.Variable.Name[0]; + if (/~DebugOnly/.test(name)) + return true; + if (/~ScopedThreadSafeStringInspector/.test(name)) + return true; + } + } + + return false; +} + +function ignoreEdgeAddressTaken(edge) +{ + // Functions which may take indirect pointers to unrooted GC things, + // but will copy them into rooted locations before calling anything + // that can GC. These parameters should usually be replaced with + // handles or mutable handles. + if (edge.Kind == "Call") { + var callee = edge.Exp[0]; + if (callee.Kind == "Var") { + var name = callee.Variable.Name[0]; + if (/js::Invoke\(/.test(name)) + return true; + } + } + + return false; +} + +// Return whether csu.method is one that we claim can never GC. +function isSuppressedVirtualMethod(csu, method) +{ + return csu == "nsISupports" && (method == "AddRef" || method == "Release"); +} + +// Ignore calls of these functions (so ignore any stack containing these) +var ignoreFunctions = { + "ptio.c:pt_MapError" : true, + "je_malloc_printf" : true, + "malloc_usable_size" : true, + "vprintf_stderr" : true, + "PR_ExplodeTime" : true, + "PR_ErrorInstallTable" : true, + "PR_SetThreadPrivate" : true, + "uint8 NS_IsMainThread()" : true, + + // Has an indirect call under it by the name "__f", which seemed too + // generic to ignore by itself. + "void* std::_Locale_impl::~_Locale_impl(int32)" : true, + + // Bug 1056410 - devirtualization prevents the standard nsISupports::Release heuristic from working + "uint32 nsXPConnect::Release()" : true, + "uint32 nsAtom::Release()" : true, + + // Allocation API + "malloc": true, + "calloc": true, + "realloc": true, + "free": true, + + // FIXME! + "NS_LogInit": true, + "NS_LogTerm": true, + "NS_LogAddRef": true, + "NS_LogRelease": true, + "NS_LogCtor": true, + "NS_LogDtor": true, + "NS_LogCOMPtrAddRef": true, + "NS_LogCOMPtrRelease": true, + + // FIXME! + "NS_DebugBreak": true, + + // Similar to heap snapshot mock classes, and GTests below. This posts a + // synchronous runnable when a GTest fails, and we are pretty sure that the + // particular runnable it posts can't even GC, but the analysis isn't + // currently smart enough to determine that. In either case, this is (a) + // only in GTests, and (b) only when the Gtest has already failed. We have + // static and dynamic checks for no GC in the non-test code, and in the test + // code we fall back to only the dynamic checks. + "void test::RingbufferDumper::OnTestPartResult(testing::TestPartResult*)" : true, + + "float64 JS_GetCurrentEmbedderTime()" : true, + + // This calls any JSObjectMovedOp for the tenured object via an indirect call. + "JSObject* js::TenuringTracer::moveToTenuredSlow(JSObject*)" : true, + + "void js::Nursery::freeMallocedBuffers()" : true, + + "void js::AutoEnterOOMUnsafeRegion::crash(uint64, int8*)" : true, + + "void mozilla::dom::WorkerPrivate::AssertIsOnWorkerThread() const" : true, + + // It would be cool to somehow annotate that nsTHashtable<T> will use + // nsTHashtable<T>::s_MatchEntry for its matchEntry function pointer, but + // there is no mechanism for that. So we will just annotate a particularly + // troublesome logging-related usage. + "EntryType* nsTHashtable<EntryType>::PutEntry(nsTHashtable<EntryType>::KeyType, const fallible_t&) [with EntryType = nsBaseHashtableET<nsCharPtrHashKey, nsAutoPtr<mozilla::LogModule> >; nsTHashtable<EntryType>::KeyType = const char*; nsTHashtable<EntryType>::fallible_t = mozilla::fallible_t]" : true, + "EntryType* nsTHashtable<EntryType>::GetEntry(nsTHashtable<EntryType>::KeyType) const [with EntryType = nsBaseHashtableET<nsCharPtrHashKey, nsAutoPtr<mozilla::LogModule> >; nsTHashtable<EntryType>::KeyType = const char*]" : true, + "EntryType* nsTHashtable<EntryType>::PutEntry(nsTHashtable<EntryType>::KeyType) [with EntryType = nsBaseHashtableET<nsPtrHashKey<const mozilla::BlockingResourceBase>, nsAutoPtr<mozilla::DeadlockDetector<mozilla::BlockingResourceBase>::OrderingEntry> >; nsTHashtable<EntryType>::KeyType = const mozilla::BlockingResourceBase*]" : true, + "EntryType* nsTHashtable<EntryType>::GetEntry(nsTHashtable<EntryType>::KeyType) const [with EntryType = nsBaseHashtableET<nsPtrHashKey<const mozilla::BlockingResourceBase>, nsAutoPtr<mozilla::DeadlockDetector<mozilla::BlockingResourceBase>::OrderingEntry> >; nsTHashtable<EntryType>::KeyType = const mozilla::BlockingResourceBase*]" : true, + + // VTune internals that lazy-load a shared library and make IndirectCalls. + "iJIT_IsProfilingActive" : true, + "iJIT_NotifyEvent": true, + + // The big hammers. + "PR_GetCurrentThread" : true, + "calloc" : true, + + // This will happen early enough in initialization to not matter. + "_PR_UnixInit" : true, + + "uint8 nsContentUtils::IsExpandedPrincipal(nsIPrincipal*)" : true, + + "void mozilla::AutoProfilerLabel::~AutoProfilerLabel(int32)" : true, + + // Stores a function pointer in an AutoProfilerLabelData struct and calls it. + // And it's in mozglue, which doesn't have access to the attributes yet. + "void mozilla::ProfilerLabelEnd(mozilla::Tuple<void*, unsigned int>*)" : true, + + // This gets into PLDHashTable function pointer territory, and should get + // set up early enough to not do anything when it matters anyway. + "mozilla::LogModule* mozilla::LogModule::Get(int8*)": true, + + // This annotation is correct, but the reasoning is still being hashed out + // in bug 1582326 comment 8 and on. + "nsCycleCollector.cpp:nsISupports* CanonicalizeXPCOMParticipant(nsISupports*)": true, + + // PLDHashTable again + "void mozilla::DeadlockDetector<T>::Add(const T*) [with T = mozilla::BlockingResourceBase]": true, + + // OOM handling during logging + "void mozilla::detail::log_print(mozilla::LogModule*, int32, int8*)": true, + + // This would need to know that the nsCOMPtr refcount will not go to zero. + "uint8 XPCJSRuntime::DescribeCustomObjects(JSObject*, JSClass*, int8[72]*)[72]) const": true, + + // As the comment says "Refcount isn't zero, so Suspect won't delete anything." + "uint64 nsCycleCollectingAutoRefCnt::incr(void*, nsCycleCollectionParticipant*) [with void (* suspect)(void*, nsCycleCollectionParticipant*, nsCycleCollectingAutoRefCnt*, bool*) = NS_CycleCollectorSuspect3; uintptr_t = long unsigned int]": true, + + // Calls MergeSort + "uint8 v8::internal::RegExpDisjunction::SortConsecutiveAtoms(v8::internal::RegExpCompiler*)": true, + + // nsIEventTarget.IsOnCurrentThreadInfallible does not get resolved, and + // this is called on non-JS threads so cannot use AutoSuppressGCAnalysis. + "uint8 nsAutoOwningEventTarget::IsCurrentThread() const": true, +}; + +function extraGCFunctions() { + return ["ffi_call"].filter(f => f in readableNames); +} + +function isProtobuf(name) +{ + return name.match(/\bgoogle::protobuf\b/) || + name.match(/\bmozilla::devtools::protobuf\b/); +} + +function isHeapSnapshotMockClass(name) +{ + return name.match(/\bMockWriter\b/) || + name.match(/\bMockDeserializedNode\b/); +} + +function isGTest(name) +{ + return name.match(/\btesting::/); +} + +function isICU(name) +{ + return name.match(/\bicu_\d+::/) || + name.match(/u(prv_malloc|prv_realloc|prv_free|case_toFullLower)_\d+/) +} + +function ignoreGCFunction(mangled) +{ + // Field calls will not be in readableNames + if (!(mangled in readableNames)) + return false; + + const fun = readableNames[mangled][0]; + + if (fun in ignoreFunctions) + return true; + + // The protobuf library, and [de]serialization code generated by the + // protobuf compiler, uses a _ton_ of function pointers but they are all + // internal. The same is true for ICU. Easiest to just ignore that mess + // here. + if (isProtobuf(fun) || isICU(fun)) + return true; + + // Ignore anything that goes through heap snapshot GTests or mocked classes + // used in heap snapshot GTests. GTest and GMock expose a lot of virtual + // methods and function pointers that could potentially GC after an + // assertion has already failed (depending on user-provided code), but don't + // exhibit that behavior currently. For non-test code, we have dynamic and + // static checks that ensure we don't GC. However, for test code we opt out + // of static checks here, because of the above stated GMock/GTest issues, + // and rely on only the dynamic checks provided by AutoAssertCannotGC. + if (isHeapSnapshotMockClass(fun) || isGTest(fun)) + return true; + + // Templatized function + if (fun.includes("void nsCOMPtr<T>::Assert_NoQueryNeeded()")) + return true; + + // Bug 1577915 - Sixgill is ignoring a template param that makes its CFG + // impossible. + if (fun.includes("UnwrapObjectInternal") && fun.includes("mayBeWrapper = false")) + return true; + + // These call through an 'op' function pointer. + if (fun.includes("js::WeakMap<Key, Value, HashPolicy>::getDelegate(")) + return true; + + // TODO: modify refillFreeList<NoGC> to not need data flow analysis to + // understand it cannot GC. As of gcc 6, the same problem occurs with + // tryNewTenuredThing, tryNewNurseryObject, and others. + if (/refillFreeList|tryNew/.test(fun) && /= js::NoGC/.test(fun)) + return true; + + return false; +} + +function stripUCSAndNamespace(name) +{ + name = name.replace(/(struct|class|union|const) /g, ""); + name = name.replace(/(js::ctypes::|js::|JS::|mozilla::dom::|mozilla::)/g, ""); + return name; +} + +function extraRootedGCThings() +{ + return [ 'JSAddonId' ]; +} + +function extraRootedPointers() +{ + return [ + ]; +} + +function isRootedGCPointerTypeName(name) +{ + name = stripUCSAndNamespace(name); + + if (name.startsWith('MaybeRooted<')) + return /\(js::AllowGC\)1u>::RootType/.test(name); + + return false; +} + +function isUnsafeStorage(typeName) +{ + typeName = stripUCSAndNamespace(typeName); + return typeName.startsWith('UniquePtr<'); +} + +// If edgeType is a constructor type, return whatever limits it implies for its +// scope (or zero if not matching). +function isLimitConstructor(typeInfo, edgeType, varName) +{ + // Check whether this could be a constructor + if (edgeType.Kind != 'Function') + return 0; + if (!('TypeFunctionCSU' in edgeType)) + return 0; + if (edgeType.Type.Kind != 'Void') + return 0; + + // Check whether the type is a known suppression type. + var type = edgeType.TypeFunctionCSU.Type.Name; + let limit = 0; + if (type in typeInfo.GCSuppressors) + limit = limit | LIMIT_CANNOT_GC; + + // And now make sure this is the constructor, not some other method on a + // suppression type. varName[0] contains the qualified name. + var [ mangled, unmangled ] = splitFunction(varName[0]); + if (mangled.search(/C\d[EI]/) == -1) + return 0; // Mangled names of constructors have C<num>E or C<num>I + var m = unmangled.match(/([~\w]+)(?:<.*>)?\(/); + if (!m) + return 0; + var type_stem = type.replace(/\w+::/g, '').replace(/\<.*\>/g, ''); + if (m[1] != type_stem) + return 0; + + return limit; +} + +// nsISupports subclasses' methods may be scriptable (or overridden +// via binary XPCOM), and so may GC. But some fields just aren't going +// to get overridden with something that can GC. +function isOverridableField(staticCSU, csu, field) +{ + if (csu != 'nsISupports') + return false; + + // Now that binary XPCOM is dead, all these annotations should be replaced + // with something based on bug 1347999. + if (field == 'GetCurrentJSContext') + return false; + if (field == 'IsOnCurrentThread') + return false; + if (field == 'GetNativeContext') + return false; + if (field == "GetGlobalJSObject") + return false; + if (field == "GetGlobalJSObjectPreserveColor") + return false; + if (field == "GetIsMainThread") + return false; + if (field == "GetThreadFromPRThread") + return false; + if (field == "DocAddSizeOfIncludingThis") + return false; + if (field == "ConstructUbiNode") + return false; + + // Fields on the [builtinclass] nsIPrincipal + if (field == "GetSiteOrigin") + return false; + if (field == "GetDomain") + return false; + if (field == "GetBaseDomain") + return false; + if (field == "GetOriginNoSuffix") + return false; + + // Fields on nsIURI + if (field == "GetScheme") + return false; + if (field == "GetAsciiHostPort") + return false; + if (field == "GetAsciiSpec") + return false; + if (field == "SchemeIs") + return false; + + if (staticCSU == 'nsIXPCScriptable' && field == "GetScriptableFlags") + return false; + if (staticCSU == 'nsIXPConnectJSObjectHolder' && field == 'GetJSObject') + return false; + if (staticCSU == 'nsIXPConnect' && field == 'GetSafeJSContext') + return false; + + // nsIScriptSecurityManager is not [builtinclass], but smaug says "the + // interface definitely should be builtinclass", which is good enough. + if (staticCSU == 'nsIScriptSecurityManager' && field == 'IsSystemPrincipal') + return false; + + if (staticCSU == 'nsIScriptContext') { + if (field == 'GetWindowProxy' || field == 'GetWindowProxyPreserveColor') + return false; + } + return true; +} + +function listNonGCPointers() { + return [ + // Safe only because jsids are currently only made from pinned strings. + 'NPIdentifier', + ]; +} + +function isJSNative(mangled) +{ + // _Z...E = function + // 9JSContext = JSContext* + // j = uint32 + // PN2JS5Value = JS::Value* + // P = pointer + // N2JS = JS:: + // 5Value = Value + return mangled.endsWith("P9JSContextjPN2JS5ValueE") && mangled.startsWith("_Z"); +} diff --git a/js/src/devtools/rootAnalysis/build.js b/js/src/devtools/rootAnalysis/build.js new file mode 100644 index 0000000000..902ae1e32f --- /dev/null +++ b/js/src/devtools/rootAnalysis/build.js @@ -0,0 +1,15 @@ +#!/bin/sh +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + + +set -e + +cd $SOURCE +./mach configure +./mach build export +./mach build -X nsprpub mfbt memory memory/mozalloc modules/zlib mozglue js/src xpcom/glue js/ductwork/debugger js/xpconnect/loader js/xpconnect/wrappers js/xpconnect/src +status=$? +echo "[[[[ build.js complete, exit code $status ]]]]" +exit $status diff --git a/js/src/devtools/rootAnalysis/build/sixgill-b2g.manifest b/js/src/devtools/rootAnalysis/build/sixgill-b2g.manifest new file mode 100644 index 0000000000..1ecb5d0665 --- /dev/null +++ b/js/src/devtools/rootAnalysis/build/sixgill-b2g.manifest @@ -0,0 +1,10 @@ +[ +{ +"hg_id" : "ec7b7d2442e8", +"algorithm" : "sha512", +"digest" : "49627d734df52cb9e7319733da5a6be1812b9373355dc300ee5600b431122570e00d380d50c7c5b5003c462c2c2cb022494b42c4ad00f8eba01c2259cbe6e502", +"filename" : "sixgill.tar.xz", +"size" : 2628868, +"unpack" : true +} +] diff --git a/js/src/devtools/rootAnalysis/build/sixgill.manifest b/js/src/devtools/rootAnalysis/build/sixgill.manifest new file mode 100644 index 0000000000..49ccdcbd3f --- /dev/null +++ b/js/src/devtools/rootAnalysis/build/sixgill.manifest @@ -0,0 +1,10 @@ +[ +{ +"digest" : "2e56a3cf84764b8e63720e5f961cff7ba8ba5cf2f353dac55c69486489bcd89f53a757e09469a07700b80cd09f09666c2db4ce375b67060ac3be967714597231", +"size" : 2629600, +"hg_id" : "221d0d2eead9", +"unpack" : true, +"filename" : "sixgill.tar.xz", +"algorithm" : "sha512" +} +] diff --git a/js/src/devtools/rootAnalysis/callgraph.js b/js/src/devtools/rootAnalysis/callgraph.js new file mode 100644 index 0000000000..9b198791e0 --- /dev/null +++ b/js/src/devtools/rootAnalysis/callgraph.js @@ -0,0 +1,247 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +loadRelativeToScript('utility.js'); +loadRelativeToScript('annotations.js'); +loadRelativeToScript('CFG.js'); + +// Map from csu => set of immediate subclasses +var subclasses = new Map(); + +// Map from csu => set of immediate superclasses +var superclasses = new Map(); + +// Map from "csu.name:nargs" => set of full method name +var virtualDefinitions = new Map(); + +// Every virtual method declaration, anywhere. +// +// field : CFG of the field +var virtualResolutionsSeen = new Set(); + +// map is a map from names to sets of entries. +function addToNamedSet(map, name, entry) +{ + if (!map.has(name)) + map.set(name, new Set()); + map.get(name).add(entry); +} + +function fieldKey(csuName, field) +{ + // This makes a minimal attempt at dealing with overloading: it will not + // conflate two virtual methods with differing numbers of arguments. So + // far, that is all that has been needed. + var nargs = 0; + if (field.Type.Kind == "Function" && "TypeFunctionArguments" in field.Type) + nargs = field.Type.TypeFunctionArguments.Type.length; + return csuName + ":" + field.Name[0] + ":" + nargs; +} + +// CSU is "Class/Struct/Union" +function processCSU(csuName, csu) +{ + if (!("FunctionField" in csu)) + return; + for (const field of csu.FunctionField) { + if (1 in field.Field) { + const superclass = field.Field[1].Type.Name; + const subclass = field.Field[1].FieldCSU.Type.Name; + assert(subclass == csuName); + addToNamedSet(subclasses, superclass, subclass); + addToNamedSet(superclasses, subclass, superclass); + } + + if ("Variable" in field) { + // Note: not dealing with overloading correctly. + const name = field.Variable.Name[0]; + addToNamedSet(virtualDefinitions, fieldKey(csuName, field.Field[0]), name); + } + } +} + +// Return the nearest ancestor method definition, or all nearest definitions in +// the case of multiple inheritance. +function nearestAncestorMethods(csu, field) +{ + const key = fieldKey(csu, field); + + if (virtualDefinitions.has(key)) + return new Set(virtualDefinitions.get(key)); + + const functions = new Set(); + if (superclasses.has(csu)) { + for (const parent of superclasses.get(csu)) + functions.update(nearestAncestorMethods(parent, field)); + } + + return functions; +} + +// Return [ instantiations, limits ], where instantiations is a Set of all +// possible implementations of 'field' given static type 'initialCSU', plus +// null if arbitrary other implementations are possible, and limits gives +// information about what things are not possible within it (currently, that it +// cannot GC). +function findVirtualFunctions(initialCSU, field) +{ + const fieldName = field.Name[0]; + const worklist = [initialCSU]; + const functions = new Set(); + + // Loop through all methods of initialCSU (by looking at all methods of ancestor csus). + // + // If field is nsISupports::AddRef or ::Release, return an empty list and a + // boolean that says we assert that it cannot GC. + // + // If this is a method that is annotated to be dangerous (eg, it could be + // overridden with an implementation that could GC), then use null as a + // signal value that it should be considered to GC, even though we'll also + // collect all of the instantiations for other purposes. + + while (worklist.length) { + const csu = worklist.pop(); + if (isSuppressedVirtualMethod(csu, fieldName)) + return [ new Set(), LIMIT_CANNOT_GC ]; + if (isOverridableField(initialCSU, csu, fieldName)) { + // We will still resolve the virtual function call, because it's + // nice to have as complete a callgraph as possible for other uses. + // But push a token saying that we can run arbitrary code. + functions.add(null); + } + + if (superclasses.has(csu)) + worklist.push(...superclasses.get(csu)); + } + + // Now return a list of all the instantiations of the method named 'field' + // that could execute on an instance of initialCSU or a descendant class. + + // Start with the class itself, or if it doesn't define the method, all + // nearest ancestor definitions. + functions.update(nearestAncestorMethods(initialCSU, field)); + + // Then recurse through all descendants to add in their definitions. + + worklist.push(initialCSU); + while (worklist.length) { + const csu = worklist.pop(); + const key = fieldKey(csu, field); + + if (virtualDefinitions.has(key)) + functions.update(virtualDefinitions.get(key)); + + if (subclasses.has(csu)) + worklist.push(...subclasses.get(csu)); + } + + return [ functions, LIMIT_NONE ]; +} + +// Return a list of all callees that the given edge might be a call to. Each +// one is represented by an object with a 'kind' field that is one of +// ('direct', 'field', 'resolved-field', 'indirect', 'unknown'), though note +// that 'resolved-field' is really a global record of virtual method +// resolutions, indepedent of this particular edge. +function getCallees(edge) +{ + if (edge.Kind != "Call") + return []; + + const callee = edge.Exp[0]; + if (callee.Kind == "Var") { + assert(callee.Variable.Kind == "Func"); + return [{'kind': 'direct', 'name': callee.Variable.Name[0]}]; + } + + if (callee.Kind == "Int") + return []; // Intentional crash + + assert(callee.Kind == "Drf"); + const called = callee.Exp[0]; + if (called.Kind == "Var") { + // indirect call through a variable. + return [{'kind': "indirect", 'variable': callee.Exp[0].Variable.Name[0]}]; + } + + if (called.Kind != "Fld") { + // unknown call target. + return [{'kind': "unknown"}]; + } + + const callees = []; + const field = callee.Exp[0].Field; + const fieldName = field.Name[0]; + const csuName = field.FieldCSU.Type.Name; + let functions; + let limits = LIMIT_NONE; + if ("FieldInstanceFunction" in field) { + [ functions, limits ] = findVirtualFunctions(csuName, field); + callees.push({'kind': "field", 'csu': csuName, 'field': fieldName, + 'limits': limits, 'isVirtual': true}); + } else { + functions = new Set([null]); // field call + } + + // Known set of virtual call targets. Treat them as direct calls to all + // possible resolved types, but also record edges from this field call to + // each final callee. When the analysis is checking whether an edge can GC + // and it sees an unrooted pointer held live across this field call, it + // will know whether any of the direct callees can GC or not. + const targets = []; + let fullyResolved = true; + for (const name of functions) { + if (name === null) { + // Unknown set of call targets, meaning either a function pointer + // call ("field call") or a virtual method that can be overridden + // in extensions. Use the isVirtual property so that callers can + // tell which case holds. + callees.push({'kind': "field", 'csu': csuName, 'field': fieldName, + 'limits': limits, + 'isVirtual': "FieldInstanceFunction" in field}); + fullyResolved = false; + } else { + targets.push({'kind': "direct", name, limits }); + } + } + if (fullyResolved) + callees.push({'kind': "resolved-field", 'csu': csuName, 'field': fieldName, 'callees': targets}); + + return callees; +} + +function loadTypes(type_xdb_filename) { + const xdb = xdbLibrary(); + xdb.open(type_xdb_filename); + + const minStream = xdb.min_data_stream(); + const maxStream = xdb.max_data_stream(); + + for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) { + const csu = xdb.read_key(csuIndex); + const data = xdb.read_entry(csu); + const json = JSON.parse(data.readString()); + processCSU(csu.readString(), json[0]); + + xdb.free_string(csu); + xdb.free_string(data); + } +} + +function loadTypesWithCache(type_xdb_filename, cache_filename) { + try { + const cacheAB = os.file.readFile(cache_filename, "binary"); + const cb = serialize(); + cb.clonebuffer = cacheAB.buffer; + const cacheData = deserialize(cb); + subclasses = cacheData.subclasses; + superclasses = cacheData.superclasses; + virtualDefinitions = cacheData.virtualDefinitions; + } catch (e) { + loadTypes(type_xdb_filename); + const cb = serialize({subclasses, superclasses, virtualDefinitions}); + os.file.writeTypedArrayToFile(cache_filename, + new Uint8Array(cb.arraybuffer)); + } +} diff --git a/js/src/devtools/rootAnalysis/computeCallgraph.js b/js/src/devtools/rootAnalysis/computeCallgraph.js new file mode 100644 index 0000000000..a622d38e1a --- /dev/null +++ b/js/src/devtools/rootAnalysis/computeCallgraph.js @@ -0,0 +1,342 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +loadRelativeToScript('callgraph.js'); + +var theFunctionNameToFind; +if (scriptArgs[0] == '--function' || scriptArgs[0] == '-f') { + theFunctionNameToFind = scriptArgs[1]; + scriptArgs = scriptArgs.slice(2); +} + +var typeInfo_filename = scriptArgs[0] || "typeInfo.txt"; +var callgraphOut_filename = scriptArgs[1] || "callgraph.txt"; + +var origOut = os.file.redirect(callgraphOut_filename); + +var memoized = new Map(); +var memoizedCount = 0; + +var JSNativeCaller = Object.create(null); +var JSNatives = []; + +var unmangled2id = new Set(); + +function getId(name) +{ + let id = memoized.get(name); + if (id !== undefined) + return id; + + id = memoized.size + 1; + memoized.set(name, id); + print(`#${id} ${name}`); + + return id; +} + +function functionId(name) +{ + const [mangled, unmangled] = splitFunction(name); + const id = getId(mangled); + + // Only produce a mangled -> unmangled mapping once, unless there are + // multiple unmangled names for the same mangled name. + if (unmangled2id.has(unmangled)) + return id; + + print(`= ${id} ${unmangled}`); + unmangled2id.add(unmangled); + return id; +} + +var lastline; +function printOnce(line) +{ + if (line != lastline) { + print(line); + lastline = line; + } +} + +// Returns a table mapping function name to lists of +// [annotation-name, annotation-value] pairs: +// { function-name => [ [annotation-name, annotation-value] ] } +// +// Note that sixgill will only store certain attributes (annotation-names), so +// this won't be *all* the attributes in the source, just the ones that sixgill +// watches for. +function getAllAttributes(body) +{ + var all_annotations = {}; + for (var v of (body.DefineVariable || [])) { + if (v.Variable.Kind != 'Func') + continue; + var name = v.Variable.Name[0]; + var annotations = all_annotations[name] = []; + + for (var ann of (v.Type.Annotation || [])) { + annotations.push(ann.Name); + } + } + + return all_annotations; +} + +// Get just the annotations understood by the hazard analysis. +function getAnnotations(functionName, body) { + var tags = new Set(); + var attributes = getAllAttributes(body); + if (functionName in attributes) { + for (var [ annName, annValue ] of attributes[functionName]) { + if (annName == 'annotate') + tags.add(annValue); + } + } + return tags; +} + +// Scan through a function body, pulling out all annotations and calls and +// recording them in callgraph.txt. +function processBody(functionName, body) +{ + if (!('PEdge' in body)) + return; + + + for (var tag of getAnnotations(functionName, body).values()) { + print("T " + functionId(functionName) + " " + tag); + if (tag == "Calls JSNatives") + JSNativeCaller[functionName] = true; + } + + // Set of all callees that have been output so far, in order to suppress + // repeated callgraph edges from being recorded. This uses a Map from + // callees to limit sets, because we don't want a limited edge to prevent + // an unlimited edge from being recorded later. (So an edge will be skipped + // if it exists and is at least as limited as the previously seen edge.) + // + // Limit sets are implemented as integers interpreted as bitfields. + // + var seen = new Map(); + + lastline = null; + for (var edge of body.PEdge) { + if (edge.Kind != "Call") + continue; + + // The limits (eg LIMIT_CANNOT_GC) are determined by whatever RAII + // scopes might be active, which have been computed previously for all + // points in the body. + var edgeLimited = body.limits[edge.Index[0]] | 0; + + for (var callee of getCallees(edge)) { + // Individual callees may have additional limits. The only such + // limit currently is that nsISupports.{AddRef,Release} are assumed + // to never GC. + const limits = edgeLimited | callee.limits; + let prologue = limits ? `/${limits} ` : ""; + prologue += functionId(functionName) + " "; + if (callee.kind == 'direct') { + const prev_limits = seen.has(callee.name) ? seen.get(callee.name) : LIMIT_UNVISITED; + if (prev_limits & ~limits) { + // Only output an edge if it loosens a limit. + seen.set(callee.name, prev_limits & limits); + printOnce("D " + prologue + functionId(callee.name)); + } + } else if (callee.kind == 'field') { + var { csu, field, isVirtual } = callee; + const tag = isVirtual ? 'V' : 'F'; + const fullfield = `${csu}.${field}`; + printOnce(`${tag} ${prologue}${getId(fullfield)} CLASS ${csu} FIELD ${field}`); + } else if (callee.kind == 'resolved-field') { + // Fully-resolved field (virtual method) call. Record the + // callgraph edges. Do not consider limits, since they are + // local to this callsite and we are writing out a global + // record here. + // + // Any field call that does *not* have an R entry must be + // assumed to call anything. + var { csu, field, callees } = callee; + var fullFieldName = csu + "." + field; + if (!virtualResolutionsSeen.has(fullFieldName)) { + virtualResolutionsSeen.add(fullFieldName); + for (var target of callees) + printOnce("R " + getId(fullFieldName) + " " + functionId(target.name)); + } + } else if (callee.kind == 'indirect') { + printOnce("I " + prologue + "VARIABLE " + callee.variable); + } else if (callee.kind == 'unknown') { + printOnce("I " + prologue + "VARIABLE UNKNOWN"); + } else { + printErr("invalid " + callee.kind + " callee"); + debugger; + } + } + } +} + +var typeInfo = loadTypeInfo(typeInfo_filename); + +loadTypes("src_comp.xdb"); + +var xdb = xdbLibrary(); +xdb.open("src_body.xdb"); + +printErr("Finished loading data structures"); + +var minStream = xdb.min_data_stream(); +var maxStream = xdb.max_data_stream(); + +if (theFunctionNameToFind) { + var index = xdb.lookup_key(theFunctionNameToFind); + if (!index) { + printErr("Function not found"); + quit(1); + } + minStream = maxStream = index; +} + +function process(functionName, functionBodies) +{ + for (var body of functionBodies) + body.limits = []; + + for (var body of functionBodies) { + for (var [pbody, id, limits] of allRAIIGuardedCallPoints(typeInfo, functionBodies, body, isLimitConstructor)) { + pbody.limits[id] = limits; + } + } + + for (var body of functionBodies) + processBody(functionName, body); + + // GCC generates multiple constructors and destructors ("in-charge" and + // "not-in-charge") to handle virtual base classes. They are normally + // identical, and it appears that GCC does some magic to alias them to the + // same thing. But this aliasing is not visible to the analysis. So we'll + // add a dummy call edge from "foo" -> "foo *INTERNAL* ", since only "foo" + // will show up as called but only "foo *INTERNAL* " will be emitted in the + // case where the constructors are identical. + // + // This is slightly conservative in the case where they are *not* + // identical, but that should be rare enough that we don't care. + var markerPos = functionName.indexOf(internalMarker); + if (markerPos > 0) { + var inChargeXTor = functionName.replace(internalMarker, ""); + printOnce("D " + functionId(inChargeXTor) + " " + functionId(functionName)); + } + + const [ mangled, unmangled ] = splitFunction(functionName); + + // Further note: from https://itanium-cxx-abi.github.io/cxx-abi/abi.html the + // different kinds of constructors/destructors are: + // C1 # complete object constructor + // C2 # base object constructor + // C3 # complete object allocating constructor + // D0 # deleting destructor + // D1 # complete object destructor + // D2 # base object destructor + // + // In actual practice, I have observed C4 and D4 xtors generated by gcc + // 4.9.3 (but not 4.7.3). The gcc source code says: + // + // /* This is the old-style "[unified]" constructor. + // In some cases, we may emit this function and call + // it from the clones in order to share code and save space. */ + // + // Unfortunately, that "call... from the clones" does not seem to appear in + // the CFG we get from GCC. So if we see a C4 constructor or D4 destructor, + // inject an edge to it from C1, C2, and C3 (or D1, D2, and D3). (Note that + // C3 isn't even used in current GCC, but add the edge anyway just in + // case.) + // + // from gcc/cp/mangle.c: + // + // <special-name> ::= D0 # deleting (in-charge) destructor + // ::= D1 # complete object (in-charge) destructor + // ::= D2 # base object (not-in-charge) destructor + // <special-name> ::= C1 # complete object constructor + // ::= C2 # base object constructor + // ::= C3 # complete object allocating constructor + // + // Currently, allocating constructors are never used. + // + if (functionName.indexOf("C4") != -1) { + // E terminates the method name (and precedes the method parameters). + // If eg "C4E" shows up in the mangled name for another reason, this + // will create bogus edges in the callgraph. But it will affect little + // and is somewhat difficult to avoid, so we will live with it. + // + // Another possibility! A templatized constructor will contain C4I...E + // for template arguments. + // + for (let [synthetic, variant, desc] of [ + ['C4E', 'C1E', 'complete_ctor'], + ['C4E', 'C2E', 'base_ctor'], + ['C4E', 'C3E', 'complete_alloc_ctor'], + ['C4I', 'C1I', 'complete_ctor'], + ['C4I', 'C2I', 'base_ctor'], + ['C4I', 'C3I', 'complete_alloc_ctor']]) + { + if (mangled.indexOf(synthetic) == -1) + continue; + + let variant_mangled = mangled.replace(synthetic, variant); + let variant_full = `${variant_mangled}$${unmangled} [[${desc}]]`; + printOnce("D " + functionId(variant_full) + " " + functionId(functionName)); + } + } + + // For destructors: + // + // I've never seen D4Ev() + D4Ev(int32), only one or the other. So + // for a D4Ev of any sort, create: + // + // D0() -> D1() # deleting destructor calls complete destructor, then deletes + // D1() -> D2() # complete destructor calls base destructor, then destroys virtual bases + // D2() -> D4(?) # base destructor might be aliased to unified destructor + // # use whichever one is defined, in-charge or not. + // # ('?') means either () or (int32). + // + // Note that this doesn't actually make sense -- D0 and D1 should be + // in-charge, but gcc doesn't seem to give them the in-charge parameter?! + // + if (functionName.indexOf("D4Ev") != -1 && functionName.indexOf("::~") != -1) { + const not_in_charge_dtor = functionName.replace("(int32)", "()"); + const D0 = not_in_charge_dtor.replace("D4Ev", "D0Ev") + " [[deleting_dtor]]"; + const D1 = not_in_charge_dtor.replace("D4Ev", "D1Ev") + " [[complete_dtor]]"; + const D2 = not_in_charge_dtor.replace("D4Ev", "D2Ev") + " [[base_dtor]]"; + printOnce("D " + functionId(D0) + " " + functionId(D1)); + printOnce("D " + functionId(D1) + " " + functionId(D2)); + printOnce("D " + functionId(D2) + " " + functionId(functionName)); + } + + if (isJSNative(mangled)) + JSNatives.push(functionName); +} + +function postprocess_callgraph() { + for (const caller of Object.keys(JSNativeCaller)) { + const caller_id = functionId(caller); + for (const callee of JSNatives) + printOnce(`D ${caller_id} ${functionId(callee)}`); + } +} + +for (var nameIndex = minStream; nameIndex <= maxStream; nameIndex++) { + var name = xdb.read_key(nameIndex); + var data = xdb.read_entry(name); + process(name.readString(), JSON.parse(data.readString())); + xdb.free_string(name); + xdb.free_string(data); +} + +postprocess_callgraph(); + +os.file.close(os.file.redirect(origOut)); diff --git a/js/src/devtools/rootAnalysis/computeGCFunctions.js b/js/src/devtools/rootAnalysis/computeGCFunctions.js new file mode 100644 index 0000000000..9a693df677 --- /dev/null +++ b/js/src/devtools/rootAnalysis/computeGCFunctions.js @@ -0,0 +1,76 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +loadRelativeToScript('utility.js'); +loadRelativeToScript('annotations.js'); +loadRelativeToScript('loadCallgraph.js'); + +if (typeof scriptArgs[0] != 'string') + throw "Usage: computeGCFunctions.js <callgraph.txt> <out:gcFunctions.txt> <out:gcFunctions.lst> <out:gcEdges.txt> <out:limitedFunctions.lst>"; + +var start = "Time: " + new Date; + +var callgraph_filename = scriptArgs[0]; +var gcFunctions_filename = scriptArgs[1] || "gcFunctions.txt"; +var gcFunctionsList_filename = scriptArgs[2] || "gcFunctions.lst"; +var gcEdges_filename = scriptArgs[3] || "gcEdges.txt"; +var limitedFunctionsList_filename = scriptArgs[4] || "limitedFunctions.lst"; + +loadCallgraph(callgraph_filename); + +printErr("Writing " + gcFunctions_filename); +redirect(gcFunctions_filename); + +for (var name in gcFunctions) { + for (let readable of (readableNames[name] || [])) { + print(""); + print("GC Function: " + name + "$" + readable); + let current = name; + do { + current = gcFunctions[current]; + if (current in readableNames) + print(" " + readableNames[current][0]); + else + print(" " + current); + } while (current in gcFunctions); + } +} + +printErr("Writing " + gcFunctionsList_filename); +redirect(gcFunctionsList_filename); +for (var name in gcFunctions) { + if (name in readableNames) { + for (var readable of readableNames[name]) + print(name + "$" + readable); + } else { + print(name); + } +} + +// gcEdges is a list of edges that can GC for more specific reasons than just +// calling a function that is in gcFunctions.txt. +// +// Right now, it is unused. It was meant for ~AutoRealm when it might +// wrap an exception, but anything held live across ~AC will have to be held +// live across the corresponding constructor (and hence the whole scope of the +// AC), and in that case it'll be held live across whatever could create an +// exception within the AC scope. So ~AC edges are redundant. I will leave the +// stub machinery here for now. +printErr("Writing " + gcEdges_filename); +redirect(gcEdges_filename); +for (var block in gcEdges) { + for (var edge in gcEdges[block]) { + var func = gcEdges[block][edge]; + print([ block, edge, func ].join(" || ")); + } +} + +printErr("Writing " + limitedFunctionsList_filename); +redirect(limitedFunctionsList_filename); +for (const [name, limits] of Object.entries(limitedFunctions)) + print(`${limits} ${name}`); diff --git a/js/src/devtools/rootAnalysis/computeGCTypes.js b/js/src/devtools/rootAnalysis/computeGCTypes.js new file mode 100644 index 0000000000..b22fb7c1fb --- /dev/null +++ b/js/src/devtools/rootAnalysis/computeGCTypes.js @@ -0,0 +1,401 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +loadRelativeToScript('utility.js'); +loadRelativeToScript('annotations.js'); + +var gcTypes_filename = scriptArgs[0] || "gcTypes.txt"; +var typeInfo_filename = scriptArgs[1] || "typeInfo.txt"; + +var typeInfo = { + 'GCPointers': [], + 'GCThings': [], + 'GCInvalidated': [], + 'NonGCTypes': {}, // unused + 'NonGCPointers': {}, + 'RootedGCThings': {}, + 'RootedPointers': {}, + 'RootedBases': {'JS::AutoGCRooter': true}, + 'InheritFromTemplateArgs': {}, + 'OtherCSUTags': {}, + 'OtherFieldTags': {}, + + // RAII types within which we should assume GC is suppressed, eg + // AutoSuppressGC. + 'GCSuppressors': {}, +}; + +var gDescriptors = new Map; // Map from descriptor string => Set of typeName + +var structureParents = {}; // Map from field => list of <parent, fieldName> +var pointerParents = {}; // Map from field => list of <parent, fieldName> +var baseClasses = {}; // Map from struct name => list of base class name strings +var subClasses = {}; // Map from struct name => list of subclass name strings + +var gcTypes = {}; // map from parent struct => Set of GC typed children +var gcPointers = {}; // map from parent struct => Set of GC typed children +var gcFields = new Map; + +var rootedPointers = {}; + +function processCSU(csu, body) +{ + for (let { 'Name': [ annType, tag ] } of (body.Annotation || [])) { + if (annType != 'annotate') + continue; + + if (tag == 'GC Pointer') + typeInfo.GCPointers.push(csu); + else if (tag == 'Invalidated by GC') + typeInfo.GCInvalidated.push(csu); + else if (tag == 'GC Thing') + typeInfo.GCThings.push(csu); + else if (tag == 'Suppressed GC Pointer') + typeInfo.NonGCPointers[csu] = true; + else if (tag == 'Rooted Pointer') + typeInfo.RootedPointers[csu] = true; + else if (tag == 'Rooted Base') + typeInfo.RootedBases[csu] = true; + else if (tag == 'Suppress GC') + typeInfo.GCSuppressors[csu] = true; + else if (tag == 'moz_inherit_type_annotations_from_template_args') + typeInfo.InheritFromTemplateArgs[csu] = true; + else + addToKeyedList(typeInfo.OtherCSUTags, csu, tag); + } + + for (let { 'Base': base } of (body.CSUBaseClass || [])) + addBaseClass(csu, base); + + for (const field of (body.DataField || [])) { + var type = field.Field.Type; + var fieldName = field.Field.Name[0]; + if (type.Kind == "Pointer") { + var target = type.Type; + if (target.Kind == "CSU") + addNestedPointer(csu, target.Name, fieldName); + } + if (type.Kind == "Array") { + var target = type.Type; + if (target.Kind == "CSU") + addNestedStructure(csu, target.Name, fieldName); + } + if (type.Kind == "CSU") + addNestedStructure(csu, type.Name, fieldName); + + for (const { 'Name': [ annType, tag ] } of (field.Annotation || [])) { + if (!(csu in typeInfo.OtherFieldTags)) + typeInfo.OtherFieldTags[csu] = []; + addToKeyedList(typeInfo.OtherFieldTags[csu], fieldName, tag); + } + } + + for (const funcfield of (body.FunctionField || [])) { + const fields = funcfield.Field; + // Pure virtual functions will not have field.Variable; others will. + for (const field of funcfield.Field) { + for (const {'Name': [annType, tag]} of (field.Annotation || [])) { + if (!(csu in typeInfo.OtherFieldTags)) + typeInfo.OtherFieldTags[csu] = {}; + addToKeyedList(typeInfo.OtherFieldTags[csu], field.Name[0], tag); + } + } + } +} + +// csu.field is of type inner +function addNestedStructure(csu, inner, field) +{ + if (!(inner in structureParents)) + structureParents[inner] = []; + + // Skip fields that are really base classes, to avoid duplicating the base + // fields; addBaseClass already added a "base-N" name. + if (field.match(/^field:\d+$/) && (csu in baseClasses) && (baseClasses[csu].indexOf(inner) != -1)) + return; + + structureParents[inner].push([ csu, field ]); +} + +function addBaseClass(csu, base) { + if (!(csu in baseClasses)) + baseClasses[csu] = []; + baseClasses[csu].push(base); + if (!(base in subClasses)) + subClasses[base] = []; + subClasses[base].push(csu); + var k = baseClasses[csu].length; + addNestedStructure(csu, base, `<base-${k}>`); +} + +function addNestedPointer(csu, inner, field) +{ + if (!(inner in pointerParents)) + pointerParents[inner] = []; + pointerParents[inner].push([ csu, field ]); +} + +var xdb = xdbLibrary(); +xdb.open("src_comp.xdb"); + +var minStream = xdb.min_data_stream(); +var maxStream = xdb.max_data_stream(); + +for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) { + var csu = xdb.read_key(csuIndex); + var data = xdb.read_entry(csu); + var json = JSON.parse(data.readString()); + assert(json.length == 1); + processCSU(csu.readString(), json[0]); + + xdb.free_string(csu); + xdb.free_string(data); +} + +for (const typename of extraRootedGCThings()) + typeInfo.RootedGCThings[typename] = true; + +for (const typename of extraRootedPointers()) + typeInfo.RootedPointers[typename] = true; + +// Everything that inherits from a "Rooted Base" is considered to be rooted. +// This is for things like CustomAutoRooter and its subclasses. +var basework = Object.keys(typeInfo.RootedBases); +while (basework.length) { + const base = basework.pop(); + typeInfo.RootedPointers[base] = true; + if (base in subClasses) + basework.push(...subClasses[base]); +} + +// Now that we have the whole hierarchy set up, add all the types and propagate +// info. +for (const csu of typeInfo.GCThings) + addGCType(csu); +for (const csu of typeInfo.GCPointers) + addGCPointer(csu); +for (const csu of typeInfo.GCInvalidated) + addGCPointer(csu); + +// GC Thing and GC Pointer annotations can be inherited from template args if +// this annotation is used. Think of Maybe<T> for example: Maybe<JSObject*> has +// the same GC rules as JSObject*. But this needs to be done in a conservative +// direction: Maybe<AutoSuppressGC> should not be regarding as suppressing GC +// (because it might still be None). +// +// Note that there is an order-dependence here that is being mostly ignored (eg +// Maybe<Maybe<Cell*>> -- if that is processed before Maybe<Cell*> is +// processed, we won't get the right answer). We'll at least sort by string +// length to make it hard to hit that case. +var inheritors = Object.keys(typeInfo.InheritFromTemplateArgs).sort((a, b) => a.length - b.length); +for (const csu of inheritors) { + // Unfortunately, we just have a string type name, not the full structure + // of a templatized type, so we will have to resort to loose (buggy) + // pattern matching. + // + // Currently, the simplest ways I know of to break this are: + // + // foo<T>::bar<U> + // foo<bar<T,U>> + // + const [_, params_str] = csu.match(/<(.*)>/); + for (let param of params_str.split(",")) { + param = param.replace(/^\s+/, '') + param = param.replace(/\s+$/, '') + const pieces = param.split("*"); + const core_type = pieces[0]; + const ptrdness = pieces.length - 1; + if (ptrdness > 1) + continue; + const paramDesc = 'template-param-' + param; + const why = '(inherited annotations from ' + param + ')'; + if (core_type in gcTypes) + markGCType(csu, paramDesc, why, ptrdness, 0, ""); + if (core_type in gcPointers) + markGCType(csu, paramDesc, why, ptrdness + 1, 0, ""); + } +} + +// "typeName is a (pointer to a)^'typePtrLevel' GC type because it contains a field +// named 'child' of type 'why' (or pointer to 'why' if fieldPtrLevel == 1), which is +// itself a GCThing or GCPointer." +function markGCType(typeName, child, why, typePtrLevel, fieldPtrLevel, indent) +{ + // Some types, like UniquePtr, do not mark/trace/relocate their contained + // pointers and so should not hold them live across a GC. UniquePtr in + // particular should be the only thing pointing to a structure containing a + // GCPointer, so nothing else can possibly trace it and it'll die when the + // UniquePtr goes out of scope. So we say that memory pointed to by a + // UniquePtr is just as unsafe as the stack for storing GC pointers. + if (!fieldPtrLevel && isUnsafeStorage(typeName)) { + // The UniquePtr itself is on the stack but when you dereference the + // contained pointer, you get to the unsafe memory that we are treating + // as if it were the stack (aka ptrLevel 0). Note that + // UniquePtr<UniquePtr<JSObject*>> is fine, so we don't want to just + // hardcode the ptrLevel. + fieldPtrLevel = -1; + } + + // Example: with: + // struct Pair { JSObject* foo; int bar; }; + // struct { Pair** info }*** + // make a call to: + // child='info' typePtrLevel=3 fieldPtrLevel=2 + // for a final ptrLevel of 5, used to later call: + // child='foo' typePtrLevel=5 fieldPtrLevel=1 + // + var ptrLevel = typePtrLevel + fieldPtrLevel; + + // ...except when > 2 levels of pointers away from an actual GC thing, stop + // searching the graph. (This would just be > 1, except that a UniquePtr + // field might still have a GC pointer.) + if (ptrLevel > 2) + return; + + if (isRootedGCPointerTypeName(typeName) && !(typeName in typeInfo.RootedPointers)) + printErr("FIXME: use in-source annotation for " + typeName); + + if (ptrLevel == 0 && (typeName in typeInfo.RootedGCThings)) + return; + if (ptrLevel == 1 && (isRootedGCPointerTypeName(typeName) || (typeName in typeInfo.RootedPointers))) + return; + + if (ptrLevel == 0) { + if (typeName in typeInfo.NonGCTypes) + return; + if (!(typeName in gcTypes)) + gcTypes[typeName] = new Set(); + gcTypes[typeName].add(why); + } else if (ptrLevel == 1) { + if (typeName in typeInfo.NonGCPointers) + return; + if (!(typeName in gcPointers)) + gcPointers[typeName] = new Set(); + gcPointers[typeName].add(why); + } + + if (ptrLevel < 2) { + if (!gcFields.has(typeName)) + gcFields.set(typeName, new Map()); + gcFields.get(typeName).set(child, [ why, fieldPtrLevel ]); + } + + if (typeName in structureParents) { + for (var field of structureParents[typeName]) { + var [ holderType, fieldName ] = field; + markGCType(holderType, fieldName, typeName, ptrLevel, 0, indent + " "); + } + } + if (typeName in pointerParents) { + for (var field of pointerParents[typeName]) { + var [ holderType, fieldName ] = field; + markGCType(holderType, fieldName, typeName, ptrLevel, 1, indent + " "); + } + } +} + +function addGCType(typeName, child, why, depth, fieldPtrLevel) +{ + markGCType(typeName, '<annotation>', '(annotation)', 0, 0, ""); +} + +function addGCPointer(typeName) +{ + markGCType(typeName, '<pointer-annotation>', '(annotation)', 1, 0, ""); +} + +// Call a function for a type and every type that contains the type in a field +// or as a base class (which internally is pretty much the same thing -- +// subclasses are structs beginning with the base class and adding on their +// local fields.) +function foreachContainingStruct(typeName, func, seen = new Set()) +{ + function recurse(container, typeName) { + if (seen.has(typeName)) + return; + seen.add(typeName); + + func(container, typeName); + + if (typeName in subClasses) { + for (const sub of subClasses[typeName]) + recurse("subclass of " + typeName, sub); + } + if (typeName in structureParents) { + for (const [holder, field] of structureParents[typeName]) + recurse(field + " : " + typeName, holder); + } + } + + recurse('<annotation>', typeName); +} + +for (var type of listNonGCPointers()) + typeInfo.NonGCPointers[type] = true; + +function explain(csu, indent, seen) { + if (!seen) + seen = new Set(); + seen.add(csu); + if (!gcFields.has(csu)) + return; + var fields = gcFields.get(csu); + + if (fields.has('<annotation>')) { + print(indent + "which is annotated as a GCThing"); + return; + } + if (fields.has('<pointer-annotation>')) { + print(indent + "which is annotated as a GCPointer"); + return; + } + for (var [ field, [ child, ptrdness ] ] of fields) { + var msg = indent; + if (field[0] == '<') + msg += "inherits from "; + else { + msg += "contains field '" + field + "' "; + if (ptrdness == -1) + msg += "(with a pointer to unsafe storage) holding a "; + else if (ptrdness == 0) + msg += "of type "; + else + msg += "pointing to type "; + } + msg += child; + print(msg); + if (!seen.has(child)) + explain(child, indent + " ", seen); + } +} + +var origOut = os.file.redirect(gcTypes_filename); + +for (var csu in gcTypes) { + print("GCThing: " + csu); + explain(csu, " "); +} +for (var csu in gcPointers) { + print("GCPointer: " + csu); + explain(csu, " "); +} + +// Redirect output to the typeInfo file and close the gcTypes file. +os.file.close(os.file.redirect(typeInfo_filename)); + +// Compute the set of types that suppress GC within their RAII scopes (eg +// AutoSuppressGC, AutoSuppressGCForAnalysis). +var seen = new Set(); +for (let csu in typeInfo.GCSuppressors) + foreachContainingStruct(csu, + (holder, typeName) => { typeInfo.GCSuppressors[typeName] = holder }, + seen); + +print(JSON.stringify(typeInfo, null, 4)); + +os.file.close(os.file.redirect(origOut)); diff --git a/js/src/devtools/rootAnalysis/dumpCFG.js b/js/src/devtools/rootAnalysis/dumpCFG.js new file mode 100644 index 0000000000..f1d52da017 --- /dev/null +++ b/js/src/devtools/rootAnalysis/dumpCFG.js @@ -0,0 +1,267 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// const cfg = loadCFG(scriptArgs[0]); +// dump_CFG(cfg); + +function loadCFG(filename) { + const data = os.file.readFile(filename); + return JSON.parse(data); +} + +function dump_CFG(cfg) { + for (const body of cfg) + dump_body(body); +} + +function dump_body(body, src, dst) { + const {BlockId,Command,DefineVariable,Index,Location,PEdge,PPoint,Version} = body; + + const [mangled, unmangled] = splitFunction(BlockId.Variable.Name[0]); + print(`${unmangled} at ${Location[0].CacheString}:${Location[0].Line}`); + + if (src === undefined) { + for (const def of DefineVariable) + print(str_definition(def)); + print(""); + } + + for (const edge of PEdge) { + if (src === undefined || edge.Index[0] == src) { + if (dst == undefined || edge.Index[1] == dst) + print(str_edge(edge, body)); + } + } +} + +function str_definition(def) { + const {Type, Variable} = def; + return `define ${str_Variable(Variable)} : ${str_Type(Type)}`; +} + +function badFormat(what, val) { + printErr("Bad format of " + what + ": " + JSON.stringify(val, null, 4)); + printErr((new Error).stack); +} + +function str_Variable(variable) { + if (variable.Kind == 'Return') + return '<returnval>'; + else if (variable.Kind == 'This') + return 'this'; + + try { + return variable.Name[1]; + } catch(e) { + badFormat("variable", variable); + } +} + +function str_Type(type) { + try { + const {Kind, Type, Name, TypeFunctionArguments} = type; + if (Kind == 'Pointer') + return str_Type(Type) + "*"; + else if (Kind == 'CSU') + return Name; + else if (Kind == 'Array') + return str_Type(Type) + "[]"; + + return Kind; + } catch(e) { + badFormat("type", type); + } +} + +var OpCodeNames = { + 'LessEqual': ['<=', '>'], + 'LessThan': ['<', '>='], + 'GreaterEqual': ['>=', '<'], + 'Greater': ['>', '<='], + 'Plus': '+', + 'Minus': '-', +}; + +function opcode_name(opcode, invert) { + if (opcode in OpCodeNames) { + const name = OpCodeNames[opcode]; + if (invert === undefined) + return name; + return name[invert ? 1 : 0]; + } else { + if (invert === undefined) + return opcode; + return (invert ? '!' : '') + opcode; + } +} + +function str_value(val, env, options) { + const {Kind, Variable, String, Exp} = val; + if (Kind == 'Var') + return str_Variable(Variable); + else if (Kind == 'Drf') { + // Suppress the vtable lookup dereference + if (Exp[0].Kind == 'Fld' && "FieldInstanceFunction" in Exp[0].Field) + return str_value(Exp[0], env); + const exp = str_value(Exp[0], env); + if (options && options.noderef) + return exp; + return "*" + exp; + } else if (Kind == 'Fld') { + const {Exp, Field} = val; + const name = Field.Name[0]; + if ("FieldInstanceFunction" in Field) { + return Field.FieldCSU.Type.Name + "." + name; + } + const container = str_value(Exp[0]); + if (container.startsWith("*")) + return container.substring(1) + "->" + name; + return container + "." + name; + } else if (Kind == 'Empty') { + return '<unknown>'; + } else if (Kind == 'Binop') { + const {OpCode} = val; + const op = opcode_name(OpCode); + return `${str_value(Exp[0], env)} ${op} ${str_value(Exp[1], env)}`; + } else if (Kind == 'Unop') { + const exp = str_value(Exp[0], env); + const {OpCode} = val; + if (OpCode == 'LogicalNot') + return `not ${exp}`; + return `${OpCode}(${exp})`; + } else if (Kind == 'Index') { + const index = str_value(Exp[1], env); + if (Exp[0].Kind == 'Drf') + return `${str_value(Exp[0], env, {noderef:true})}[${index}]`; + else + return `&${str_value(Exp[0], env)}[${index}]`; + } else if (Kind == 'NullTest') { + return `nullptr == ${str_value(Exp[0], env)}`; + } else if (Kind == "String") { + return '"' + String + '"'; + } else if (String !== undefined) { + return String; + } + badFormat("value", val); +} + +function str_thiscall_Exp(exp) { + return exp.Kind == 'Drf' ? str_value(exp.Exp[0]) + "->" : str_value(exp) + "."; +} + +function stripcsu(s) { + return s.replace("class ", "").replace("struct ", "").replace("union "); +} + +function str_call(prefix, edge, env) { + const {Exp, Type, PEdgeCallArguments, PEdgeCallInstance} = edge; + const {Kind, Type:cType, TypeFunctionArguments, TypeFunctionCSU} = Type; + + if (Kind == 'Function') { + const params = PEdgeCallArguments ? PEdgeCallArguments.Exp : []; + const strParams = params.map(str_value); + + let func; + let comment = ""; + let assign_exp; + if (PEdgeCallInstance) { + const csu = TypeFunctionCSU.Type.Name; + const method = str_value(Exp[0], env); + + // Heuristic to only display the csu for constructors + if (csu.includes(method)) { + func = stripcsu(csu) + "::" + method; + } else { + func = method; + comment = "# " + csu + "::" + method + "\n"; + } + + const {Exp: thisExp} = PEdgeCallInstance; + func = str_thiscall_Exp(thisExp) + func; + } else { + func = str_value(Exp[0]); + } + assign_exp = Exp[1]; + + let assign = ""; + if (assign_exp) { + assign = str_value(assign_exp) + " := "; + } + return `${comment}${prefix} Call ${assign}${func}(${strParams.join(", ")})`; + } + + print(JSON.stringify(edge, null, 4)); + throw "unhandled format error"; +} + +function str_assign(prefix, edge) { + const {Exp} = edge; + const [lhs, rhs] = Exp; + return `${prefix} Assign ${str_value(lhs)} := ${str_value(rhs)}`; +} + +function str_loop(prefix, edge) { + const {BlockId: {Loop}} = edge; + return `${prefix} Loop ${Loop}`; +} + +function str_assume(prefix, edge) { + const {Exp, PEdgeAssumeNonZero} = edge; + const cmp = PEdgeAssumeNonZero ? "" : "!"; + + const {Exp: aExp, Kind, OpCode} = Exp[0]; + if (Kind == 'Binop') { + const [lhs, rhs] = aExp; + const op = opcode_name(OpCode, !PEdgeAssumeNonZero); + return `${prefix} Assume ${str_value(lhs)} ${op} ${str_value(rhs)}`; + } else if (Kind == 'Unop') { + return `${prefix} Assume ${cmp}${OpCode} ${str_value(aExp[0])}`; + } else if (Kind == 'NullTest') { + return `${prefix} Assume nullptr ${cmp}== ${str_value(aExp[0])}`; + } else if (Kind == 'Drf') { + return `${prefix} Assume ${cmp}${str_value(Exp[0])}`; + } + + print(JSON.stringify(edge, null, 4)); + throw "unhandled format error"; +} + +function str_edge(edge, env) { + const {Index, Kind} = edge; + const [src, dst] = Index; + const prefix = `[${src},${dst}]`; + + if (Kind == "Call") + return str_call(prefix, edge, env); + if (Kind == 'Assign') + return str_assign(prefix, edge); + if (Kind == 'Assume') + return str_assume(prefix, edge); + if (Kind == 'Loop') + return str_loop(prefix, edge); + + print(JSON.stringify(edge, null, 4)); + throw "unhandled edge type"; +} + +function str(unknown) { + if ("Name" in unknown) { + return str_Variable(unknown); + } else if ("Index" in unknown) { + // Note: Variable also has .Index, with a different meaning. + return str_edge(unknown); + } else if ("Kind" in unknown) { + if ("BlockId" in unknown) + return str_Variable(unknown); + return str_value(unknown); + } else if ("Type" in unknown) { + return str_Type(unknown); + } + return "unknown"; +} + +function jdump(x) { + print(JSON.stringify(x, null, 4)); + quit(0); +} diff --git a/js/src/devtools/rootAnalysis/expect.b2g.json b/js/src/devtools/rootAnalysis/expect.b2g.json new file mode 100644 index 0000000000..06f2beb36f --- /dev/null +++ b/js/src/devtools/rootAnalysis/expect.b2g.json @@ -0,0 +1,3 @@ +{ + "expect-hazards": 0 +} diff --git a/js/src/devtools/rootAnalysis/expect.browser.json b/js/src/devtools/rootAnalysis/expect.browser.json new file mode 100644 index 0000000000..06f2beb36f --- /dev/null +++ b/js/src/devtools/rootAnalysis/expect.browser.json @@ -0,0 +1,3 @@ +{ + "expect-hazards": 0 +} diff --git a/js/src/devtools/rootAnalysis/expect.shell.json b/js/src/devtools/rootAnalysis/expect.shell.json new file mode 100644 index 0000000000..06f2beb36f --- /dev/null +++ b/js/src/devtools/rootAnalysis/expect.shell.json @@ -0,0 +1,3 @@ +{ + "expect-hazards": 0 +} diff --git a/js/src/devtools/rootAnalysis/explain.py b/js/src/devtools/rootAnalysis/explain.py new file mode 100755 index 0000000000..993725273c --- /dev/null +++ b/js/src/devtools/rootAnalysis/explain.py @@ -0,0 +1,129 @@ +#!/usr/bin/python3 +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this file, +# You can obtain one at http://mozilla.org/MPL/2.0/. + + +from __future__ import print_function + +import argparse +import re + +from collections import defaultdict + +parser = argparse.ArgumentParser(description="Process some integers.") +parser.add_argument("rootingHazards", nargs="?", default="rootingHazards.txt") +parser.add_argument("gcFunctions", nargs="?", default="gcFunctions.txt") +parser.add_argument("hazards", nargs="?", default="hazards.txt") +parser.add_argument("extra", nargs="?", default="unnecessary.txt") +parser.add_argument("refs", nargs="?", default="refs.txt") +args = parser.parse_args() + +num_hazards = 0 +num_refs = 0 +num_missing = 0 + +try: + with open(args.rootingHazards) as rootingHazards, open( + args.hazards, "w" + ) as hazards, open(args.extra, "w") as extra, open(args.refs, "w") as refs: + current_gcFunction = None + + # Map from a GC function name to the list of hazards resulting from + # that GC function + hazardousGCFunctions = defaultdict(list) + + # List of tuples (gcFunction, index of hazard) used to maintain the + # ordering of the hazards + hazardOrder = [] + + # Map from a hazardous GC function to the filename containing it. + fileOfFunction = {} + + for line in rootingHazards: + m = re.match(r"^Time: (.*)", line) + mm = re.match(r"^Run on:", line) + if m or mm: + print(line, file=hazards) + print(line, file=extra) + print(line, file=refs) + continue + + m = re.match(r"^Function.*has unnecessary root", line) + if m: + print(line, file=extra) + continue + + m = re.match(r"^Function.*takes unsafe address of unrooted", line) + if m: + num_refs += 1 + print(line, file=refs) + continue + + m = re.match( + r"^Function.*has unrooted.*of type.*live across GC call '(.*?)' at (\S+):\d+$", + line, + ) # NOQA: E501 + if m: + current_gcFunction = m.group(1) + hazardousGCFunctions[current_gcFunction].append(line) + hazardOrder.append( + ( + current_gcFunction, + len(hazardousGCFunctions[current_gcFunction]) - 1, + ) + ) + num_hazards += 1 + fileOfFunction[current_gcFunction] = m.group(2) + continue + + m = re.match(r"Function.*expected hazard.*but none were found", line) + if m: + num_missing += 1 + print(line + "\n", file=hazards) + continue + + if current_gcFunction: + if not line.strip(): + # Blank line => end of this hazard + current_gcFunction = None + else: + hazardousGCFunctions[current_gcFunction][-1] += line + + with open(args.gcFunctions) as gcFunctions: + gcExplanations = {} # gcFunction => stack showing why it can GC + + current_func = None + explanation = None + for line in gcFunctions: + m = re.match(r"^GC Function: (.*)", line) + if m: + if current_func: + gcExplanations[current_func] = explanation + current_func = None + if m.group(1) in hazardousGCFunctions: + current_func = m.group(1) + explanation = line + elif current_func: + explanation += line + if current_func: + gcExplanations[current_func] = explanation + + for gcFunction, index in hazardOrder: + gcHazards = hazardousGCFunctions[gcFunction] + + if gcFunction in gcExplanations: + print(gcHazards[index] + gcExplanations[gcFunction], file=hazards) + else: + print(gcHazards[index], file=hazards) + +except IOError as e: + print("Failed: %s" % str(e)) + +print("Wrote %s" % args.hazards) +print("Wrote %s" % args.extra) +print("Wrote %s" % args.refs) +print( + "Found %d hazards %d unsafe references %d missing" + % (num_hazards, num_refs, num_missing) +) diff --git a/js/src/devtools/rootAnalysis/gen-hazards.sh b/js/src/devtools/rootAnalysis/gen-hazards.sh new file mode 100755 index 0000000000..7007969a14 --- /dev/null +++ b/js/src/devtools/rootAnalysis/gen-hazards.sh @@ -0,0 +1,15 @@ +#!/bin/sh + +set -e + +JOBS="$1" + +for j in $(seq $JOBS); do + env PATH=$PATH:$SIXGILL/bin XDB=$SIXGILL/bin/xdb.so $JS $ANALYZE gcFunctions.lst suppressedFunctions.lst gcTypes.txt $j $JOBS tmp.$j > rootingHazards.$j & +done + +wait + +for j in $(seq $JOBS); do + cat rootingHazards.$j +done diff --git a/js/src/devtools/rootAnalysis/loadCallgraph.js b/js/src/devtools/rootAnalysis/loadCallgraph.js new file mode 100644 index 0000000000..cfe5ab6c58 --- /dev/null +++ b/js/src/devtools/rootAnalysis/loadCallgraph.js @@ -0,0 +1,428 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +loadRelativeToScript('utility.js'); + +// Functions come out of sixgill in the form "mangled$readable". The mangled +// name is Truth. One mangled name might correspond to multiple readable names, +// for multiple reasons, including (1) sixgill/gcc doesn't always qualify types +// the same way or de-typedef the same amount; (2) sixgill's output treats +// references and pointers the same, and so doesn't distinguish them, but C++ +// treats them as separate for overloading and linking; (3) (identical) +// destructors sometimes have an int32 parameter, sometimes not. +// +// The readable names are useful because they're far more meaningful to the +// user, and are what should show up in reports and questions to mrgiggles. At +// least in most cases, it's fine to have the extra mangled name tacked onto +// the beginning for these. +// +// The strategy used is to separate out the pieces whenever they are read in, +// create a table mapping mangled names to all readable names, and use the +// mangled names in all computation -- except for limited circumstances when +// the readable name is used in annotations. +// +// Note that callgraph.txt uses a compressed representation -- each name is +// mapped to an integer, and those integers are what is recorded in the edges. +// But the integers depend on the full name, whereas the true edge should only +// consider the mangled name. And some of the names encoded in callgraph.txt +// are FieldCalls, not just function names. + +var readableNames = {}; // map from mangled name => list of readable names +var calleesOf = {}; // map from mangled => list of tuples of {'callee':mangled, 'limits':intset} +var callersOf; // map from mangled => list of tuples of {'caller':mangled, 'limits':intset} +var gcFunctions = {}; // map from mangled callee => reason +var limitedFunctions = {}; // set of mangled names (map from mangled name => limit intset) +var gcEdges = {}; + +// "Map" from identifier to mangled name, or sometimes to a Class.Field name. +var functionNames = [""]; + +var mangledToId = {}; + +// Returns whether the function was added. (It will be refused if it was +// already there, or if limits or annotations say it shouldn't be added.) +function addGCFunction(caller, reason, functionLimits) +{ + if (functionLimits[caller] & LIMIT_CANNOT_GC) + return false; + + if (ignoreGCFunction(functionNames[caller])) + return false; + + if (!(caller in gcFunctions)) { + gcFunctions[caller] = reason; + return true; + } + + return false; +} + +// Every caller->callee callsite is associated with a limit saying what is +// allowed at that callsite (eg if it's in a GC suppression zone, it would have +// LIMIT_CANNOT_GC set.) A given caller might call the same callee multiple +// times, with different limits, so we want to associate the <caller,callee> +// edge with the intersection ('AND') of all of the callsites' limits. +// +// Scan through all call edges and intersect the limits for all matching +// <caller,callee> edges (so that the result is the least limiting of all +// matching edges.) Preserve the original order. +// +// During the same scan, build callersOf from calleesOf. +function merge_repeated_calls(calleesOf) { + const callersOf = Object.create(null); + + for (const [caller, callee_limits] of Object.entries(calleesOf)) { + const ordered_callees = []; + + // callee_limits is a list of {callee,limit} objects. + const callee2limit = new Map(); + for (const {callee, limits} of callee_limits) { + const prev_limits = callee2limit.get(callee); + if (prev_limits === undefined) { + callee2limit.set(callee, limits); + ordered_callees.push(callee); + } else { + callee2limit.set(callee, prev_limits & limits); + } + } + + // Update the contents of callee_limits to contain a single entry for + // each callee, with its limits set to the AND of the limits observed + // at all callsites within this caller function. + callee_limits.length = 0; + for (const callee of ordered_callees) { + const limits = callee2limit.get(callee); + callee_limits.push({callee, limits}); + if (!(callee in callersOf)) + callersOf[callee] = []; + callersOf[callee].push({caller, limits}); + } + } + + return callersOf; +} + +function loadCallgraph(file) +{ + const fieldCallLimits = {}; + const fieldCallCSU = new Map(); // map from full field name id => csu name + const resolvedFieldCalls = new Set(); + + // set of mangled names (map from mangled name => limit intset) + var functionLimits = {}; + + let numGCCalls = 0; + + for (let line of readFileLines_gen(file)) { + line = line.replace(/\n/, ""); + + let match; + if (match = line.charAt(0) == "#" && /^\#(\d+) (.*)/.exec(line)) { + const [ _, id, mangled ] = match; + assert(functionNames.length == id); + functionNames.push(mangled); + mangledToId[mangled] = id; + continue; + } + if (match = line.charAt(0) == "=" && /^= (\d+) (.*)/.exec(line)) { + const [ _, id, readable ] = match; + const mangled = functionNames[id]; + if (mangled in readableNames) + readableNames[mangled].push(readable); + else + readableNames[mangled] = [ readable ]; + continue; + } + + let limits = 0; + // Example line: D /17 6 7 + // + // This means a direct call from 6 -> 7, but within a scope that + // applies limits 0x1 and 0x10 to the callee. + // + // Look for a limit and remove it from the line if found. + if (line.indexOf("/") != -1) { + match = /^(..)\/(\d+) (.*)/.exec(line); + line = match[1] + match[3]; + limits = match[2]|0; + } + const tag = line.charAt(0); + if (match = tag == 'I' && /^I (\d+) VARIABLE ([^\,]*)/.exec(line)) { + const caller = match[1]|0; + const name = match[2]; + if (!indirectCallCannotGC(functionNames[caller], name) && + !(limits & LIMIT_CANNOT_GC)) + { + addGCFunction(caller, "IndirectCall: " + name, functionLimits); + } + } else if (match = (tag == 'F' || tag == 'V') && /^[FV] (\d+) (\d+) CLASS (.*?) FIELD (.*)/.exec(line)) { + const caller = match[1]|0; + const fullfield = match[2]|0; + const csu = match[3]; + const fullfield_str = csu + "." + match[4]; + assert(functionNames[fullfield] == fullfield_str); + if (limits) + fieldCallLimits[fullfield] = limits; + addToKeyedList(calleesOf, caller, {callee:fullfield, limits}); + fieldCallCSU.set(fullfield, csu); + } else if (match = tag == 'D' && /^D (\d+) (\d+)/.exec(line)) { + const caller = match[1]|0; + const callee = match[2]|0; + addToKeyedList(calleesOf, caller, {callee:callee, limits:limits}); + } else if (match = tag == 'R' && /^R (\d+) (\d+)/.exec(line)) { + const callerField = match[1]|0; + const callee = match[2]|0; + // Resolved virtual functions create a dummy node for the field + // call, and callers call it. It will then call all possible + // instantiations. No additional limits are placed on the callees; + // it's as if there were a function named BaseClass.foo: + // + // void BaseClass.foo() { + // Subclass1::foo(); + // Subclass2::foo(); + // } + // + addToKeyedList(calleesOf, callerField, {callee:callee, limits:0}); + // Mark that we resolved this virtual method, so that it isn't + // assumed to call some random function that might do anything. + resolvedFieldCalls.add(callerField); + } else if (match = tag == 'T' && /^T (\d+) (.*)/.exec(line)) { + const id = match[1]|0; + let tag = match[2]; + if (tag == 'GC Call') { + addGCFunction(id, "GC", functionLimits); + numGCCalls++; + } + } else { + assert(false, "Invalid format in callgraph line: " + line); + } + } + + // Callers have a list of callees, with duplicates (if the same function is + // called more than once.) Merge the repeated calls, only keeping limits + // that are in force for *every* callsite of that callee. Also, generate + // the callersOf table at the same time. + callersOf = merge_repeated_calls(calleesOf); + + // Add in any extra functions at the end. (If we did this early, it would + // mess up the id <-> name correspondence. Also, we need to know if the + // functions even exist in the first place.) + for (var func of extraGCFunctions()) { + addGCFunction(mangledToId[func], "annotation", functionLimits); + } + + // Compute functionLimits: it should contain the set of functions that + // are *always* called within some sort of limited context (eg GC + // suppression). + + // Initialize to limited field calls. + for (var [name, limits] of Object.entries(fieldCallLimits)) { + if (limits) + functionLimits[name] = limits; + } + + // Initialize functionLimits to the set of all functions, where each one is + // maximally limited, and return a worklist containing all simple roots + // (nodes with no callers). + var roots = gather_simple_roots(functionLimits, callersOf); + + // Traverse the graph, spreading the limits down from the roots. + propagate_limits(roots, functionLimits, calleesOf); + + // There are a surprising number of "recursive roots", where there is a + // cycle of functions calling each other but not called by anything else, + // and these roots may also have descendants. Now that the above traversal + // has eliminated everything reachable from simple roots, traverse the + // remaining graph to gather up a representative function from each root + // cycle. + roots = gather_recursive_roots(roots, functionLimits, callersOf); + + // And do a final traversal starting with the recursive roots. + propagate_limits(roots, functionLimits, calleesOf); + + // Eliminate GC-limited functions from the set of functions known to GC. + for (var name in gcFunctions) { + if (functionLimits[name] & LIMIT_CANNOT_GC) + delete gcFunctions[name]; + } + + // functionLimits should now contain all functions that are always called + // in a limited context. + + // Sanity check to make sure the callgraph has some functions annotated as + // GC Calls. This is mostly a check to be sure the earlier processing + // succeeded (as opposed to, say, running on empty xdb files because you + // didn't actually compile anything interesting.) + assert(numGCCalls > 0, "No GC functions found!"); + + // Initialize the worklist to all known gcFunctions. + var worklist = []; + for (const name in gcFunctions) + worklist.push(name); + + // Include all field calls and unresolved virtual method calls. + for (const [name, csuName] of fieldCallCSU) { + if (resolvedFieldCalls.has(name)) + continue; // Skip resolved virtual functions. + const fullFieldName = functionNames[name]; + if (!fieldCallCannotGC(csuName, fullFieldName)) { + gcFunctions[name] = 'unresolved ' + fullFieldName; + worklist.push(name); + } + } + + // Recursively find all callers not always called in a GC suppression + // context, and add them to the set of gcFunctions. + while (worklist.length) { + name = worklist.shift(); + assert(name in gcFunctions, "gcFunctions does not contain " + name); + if (!(name in callersOf)) + continue; + for (const {caller, limits} of callersOf[name]) { + if (!(limits & LIMIT_CANNOT_GC)) { + if (addGCFunction(caller, name, functionLimits)) + worklist.push(caller); + } + } + } + + // Convert functionLimits to limitedFunctions (using mangled names instead + // of ids.) + + for (const [id, limits] of Object.entries(functionLimits)) + limitedFunctions[functionNames[id]] = limits; + + // The above code uses integer ids for efficiency. External code uses + // mangled names. Rewrite the various data structures to convert ids to + // mangled names. + remap_ids_to_mangled_names(); +} + +// Return a worklist of functions with no callers, and also initialize +// functionLimits to the set of all functions, each mapped to LIMIT_UNVISTED. +function gather_simple_roots(functionLimits, callersOf) { + const roots = []; + for (let callee in callersOf) + functionLimits[callee] = LIMIT_UNVISITED; + for (let caller in calleesOf) { + if (!(caller in callersOf)) { + functionLimits[caller] = LIMIT_UNVISITED; + roots.push([caller, LIMIT_NONE, 'root']); + } + } + + return roots; +} + +// Recursively traverse the callgraph from the roots. Recurse through every +// edge that weakens the limits. (Limits that entirely disappear, aka go to a +// zero intset, will be removed from functionLimits.) +function propagate_limits(worklist, functionLimits, calleesOf) { + let top = worklist.length; + while (top > 0) { + // Consider caller where (graph) -> caller -> (0 or more callees) + // 'callercaller' is for debugging. + const [caller, edge_limits, callercaller] = worklist[--top]; + const prev_limits = functionLimits[caller]; + if (prev_limits & ~edge_limits) { + // Turning off a limit (or unvisited marker). Must recurse to the + // children. But first, update this caller's limits: we just found + // out it is reachable by an unlimited path, so it must be treated + // as unlimited (with respect to that bit). + const new_limits = prev_limits & edge_limits; + if (new_limits) + functionLimits[caller] = new_limits; + else + delete functionLimits[caller]; + for (const {callee, limits} of (calleesOf[caller] || [])) + worklist[top++] = [callee, limits | edge_limits, caller]; + } + } +} + +// Mutually-recursive roots and their descendants will not have been visited, +// and will still be set to LIMIT_UNVISITED. Scan through and gather them. +function gather_recursive_roots(functionLimits, callersOf) { + const roots = []; + + // 'seen' maps functions to the most recent starting function that each was + // first reachable from, to distinguish between the current pass and passes + // for preceding functions. + // + // Consider: + // + // A <--> B --> C <-- D <--> E + // C --> F + // C --> G + // + // So there are two root cycles AB and DE, both calling C that in turn + // calls F and G. If we start at F and scan up through callers, we will + // keep going until A loops back to B and E loops back to D, and will add B + // and D as roots. Then if we scan from G, we encounter C and see that it + // was already been seen on an earlier pass. So C and everything reachable + // from it is already reachable by some root. (We need to label nodes with + // their pass because otherwise we couldn't distinguish "already seen C, + // done" from "already seen B, must be a root".) + // + const seen = new Map(); + for (var func in functionLimits) { + if (functionLimits[func] != LIMIT_UNVISITED) + continue; + + // We should only be looking at nodes with callers, since otherwise + // they would have been handled in the previous pass! + assert(callersOf[func].length > 0); + + const work = [func]; + while (work.length > 0) { + const f = work.pop(); + if (seen.has(f)) { + if (seen.get(f) == func) { + // We have traversed a cycle and reached an already-seen + // node. Treat it as a root. + roots.push([f, LIMIT_NONE, 'root']); + print(`recursive root? ${f} = ${functionNames[f]}`); + } else { + // Otherwise we hit the portion of the graph that is + // reachable from a past root. + seen.set(f, func); + } + } else { + print(`retained by recursive root? ${f} = ${functionNames[f]}`); + work.push(...callersOf[f]); + seen.set(f, func); + } + } + } + + return roots; +} + +function remap_ids_to_mangled_names() { + var tmp = gcFunctions; + gcFunctions = {}; + for (const [caller, reason] of Object.entries(tmp)) + gcFunctions[functionNames[caller]] = functionNames[reason] || reason; + + tmp = calleesOf; + calleesOf = {}; + for (const [callerId, callees] of Object.entries(calleesOf)) { + const caller = functionNames[callerId]; + for (const {calleeId, limits} of callees) + calleesOf[caller][functionNames[calleeId]] = limits; + } + + tmp = callersOf; + callersOf = {}; + for (const [calleeId, callers] of Object.entries(callersOf)) { + const callee = functionNames[calleeId]; + callersOf[callee] = {}; + for (const {callerId, limits} of callers) + callersOf[callee][functionNames[caller]] = limits; + } +} diff --git a/js/src/devtools/rootAnalysis/mach_commands.py b/js/src/devtools/rootAnalysis/mach_commands.py new file mode 100644 index 0000000000..de38df7388 --- /dev/null +++ b/js/src/devtools/rootAnalysis/mach_commands.py @@ -0,0 +1,393 @@ +# -*- coding: utf-8 -*- + +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + + +from __future__ import absolute_import, print_function, unicode_literals + +import argparse +import json +import os +import textwrap + +from mach.base import FailedCommandError, MachError +from mach.decorators import ( + CommandArgument, + CommandProvider, + Command, + SubCommand, +) +from mach.registrar import Registrar + +from mozbuild.mozconfig import MozconfigLoader +from mozbuild.base import MachCommandBase + +# Command files like this are listed in build/mach_bootstrap.py in alphabetical +# order, but we need to access commands earlier in the sorted order to grab +# their arguments. Force them to load now. +import mozbuild.artifact_commands # NOQA: F401 +import mozbuild.build_commands # NOQA: F401 + + +# Use a decorator to copy command arguments off of the named command. Instead +# of a decorator, this could be straight code that edits eg +# MachCommands.build_shell._mach_command.arguments, but that looked uglier. +def inherit_command_args(command, subcommand=None): + """Decorator for inheriting all command-line arguments from `mach build`. + + This should come earlier in the source file than @Command or @SubCommand, + because it relies on that decorator having run first.""" + + def inherited(func): + handler = Registrar.command_handlers.get(command) + if handler is not None and subcommand is not None: + handler = handler.subcommand_handlers.get(subcommand) + if handler is None: + raise MachError( + "{} command unknown or not yet loaded".format( + command if subcommand is None else command + " " + subcommand + ) + ) + func._mach_command.arguments.extend(handler.arguments) + return func + + return inherited + + +@CommandProvider +class MachCommands(MachCommandBase): + @property + def state_dir(self): + return os.environ.get("MOZBUILD_STATE_PATH", os.path.expanduser("~/.mozbuild")) + + @property + def tools_dir(self): + if os.environ.get("MOZ_FETCHES_DIR"): + # In automation, tools are provided by toolchain dependencies. + return os.path.join(os.environ["HOME"], os.environ["MOZ_FETCHES_DIR"]) + + # In development, `mach hazard bootstrap` installs the tools separately + # to avoid colliding with the "main" compiler versions, which can + # change separately (and the precompiled sixgill and compiler version + # must match exactly). + return os.path.join(self.state_dir, "hazard-tools") + + @property + def sixgill_dir(self): + return os.path.join(self.tools_dir, "sixgill") + + @property + def gcc_dir(self): + return os.path.join(self.tools_dir, "gcc") + + @property + def script_dir(self): + return os.path.join(self.topsrcdir, "js/src/devtools/rootAnalysis") + + def work_dir(self, application, given): + if given is not None: + return given + return os.path.join(self.topsrcdir, "haz-" + application) + + def ensure_dir_exists(self, dir): + os.makedirs(dir, exist_ok=True) + return dir + + # Force the use of hazard-compatible installs of tools. + def setup_env_for_tools(self, env): + gccbin = os.path.join(self.gcc_dir, "bin") + env["CC"] = os.path.join(gccbin, "gcc") + env["CXX"] = os.path.join(gccbin, "g++") + env["PATH"] = "{sixgill_dir}/usr/bin:{gccbin}:{PATH}".format( + sixgill_dir=self.sixgill_dir, gccbin=gccbin, PATH=env["PATH"] + ) + env["LD_LIBRARY_PATH"] = "{}/lib64".format(self.gcc_dir) + + @Command( + "hazards", + category="build", + order="declaration", + description="Commands for running the static analysis for GC rooting hazards", + ) + def hazards(self): + """Commands related to performing the GC rooting hazard analysis""" + print("See `mach hazards --help` for a list of subcommands") + + @inherit_command_args("artifact", "toolchain") + @SubCommand( + "hazards", + "bootstrap", + description="Install prerequisites for the hazard analysis", + ) + def bootstrap(self, **kwargs): + orig_dir = os.getcwd() + os.chdir(self.ensure_dir_exists(self.tools_dir)) + try: + kwargs["from_build"] = ("linux64-gcc-sixgill", "linux64-gcc-8") + self._mach_context.commands.dispatch( + "artifact", self._mach_context, subcommand="toolchain", **kwargs + ) + finally: + os.chdir(orig_dir) + + @inherit_command_args("build") + @SubCommand( + "hazards", "build-shell", description="Build a shell for the hazard analysis" + ) + @CommandArgument( + "--mozconfig", + default=None, + metavar="FILENAME", + help="Build with the given mozconfig.", + ) + def build_shell(self, **kwargs): + """Build a JS shell to use to run the rooting hazard analysis.""" + # The JS shell requires some specific configuration settings to execute + # the hazard analysis code, and configuration is done via mozconfig. + # Subprocesses find MOZCONFIG in the environment, so we can't just + # modify the settings in this process's loaded version. Pass it through + # the environment. + + default_mozconfig = "js/src/devtools/rootAnalysis/mozconfig.haz_shell" + mozconfig_path = ( + kwargs.pop("mozconfig", None) + or os.environ.get("MOZCONFIG") + or default_mozconfig + ) + mozconfig_path = os.path.join(self.topsrcdir, mozconfig_path) + loader = MozconfigLoader(self.topsrcdir) + mozconfig = loader.read_mozconfig(mozconfig_path) + + # Validate the mozconfig settings in case the user overrode the default. + configure_args = mozconfig["configure_args"] + if "--enable-ctypes" not in configure_args: + raise FailedCommandError( + "ctypes required in hazard JS shell, mozconfig=" + mozconfig_path + ) + + # Transmit the mozconfig location to build subprocesses. + os.environ["MOZCONFIG"] = mozconfig_path + + self.setup_env_for_tools(os.environ) + + # Set a default objdir for the shell, for developer builds. + os.environ.setdefault( + "MOZ_OBJDIR", os.path.join(self.topsrcdir, "obj-haz-shell") + ) + + return self._mach_context.commands.dispatch( + "build", self._mach_context, **kwargs + ) + + def read_json_file(self, filename): + with open(filename) as fh: + return json.load(fh) + + def ensure_shell(self, objdir): + if objdir is None: + objdir = os.path.join(self.topsrcdir, "obj-haz-shell") + + try: + binaries = self.read_json_file(os.path.join(objdir, "binaries.json")) + info = [b for b in binaries["programs"] if b["program"] == "js"][0] + return os.path.join(objdir, info["install_target"], "js") + except (OSError, KeyError): + raise FailedCommandError( + """\ +no shell found in %s -- must build the JS shell with `mach hazards build-shell` first""" + % objdir + ) + + @inherit_command_args("build") + @SubCommand( + "hazards", + "gather", + description="Gather analysis data by compiling the given application", + ) + @CommandArgument( + "--application", default="browser", help="Build the given application." + ) + @CommandArgument( + "--haz-objdir", default=None, help="Write object files to this directory." + ) + @CommandArgument( + "--work-dir", default=None, help="Directory for output and working files." + ) + def gather_hazard_data(self, **kwargs): + """Gather analysis information by compiling the tree""" + application = kwargs["application"] + objdir = kwargs["haz_objdir"] + if objdir is None: + objdir = os.environ.get("HAZ_OBJDIR") + if objdir is None: + objdir = os.path.join(self.topsrcdir, "obj-analyzed-" + application) + + work_dir = self.work_dir(application, kwargs["work_dir"]) + self.ensure_dir_exists(work_dir) + with open(os.path.join(work_dir, "defaults.py"), "wt") as fh: + data = textwrap.dedent( + """\ + analysis_scriptdir = "{script_dir}" + objdir = "{objdir}" + source = "{srcdir}" + sixgill = "{sixgill_dir}/usr/libexec/sixgill" + sixgill_bin = "{sixgill_dir}/usr/bin" + gcc_bin = "{gcc_dir}/bin" + """ + ).format( + script_dir=self.script_dir, + objdir=objdir, + srcdir=self.topsrcdir, + sixgill_dir=self.sixgill_dir, + gcc_dir=self.gcc_dir, + ) + fh.write(data) + + buildscript = " ".join( + [ + self.topsrcdir + "/mach hazards compile", + "--application=" + application, + "--haz-objdir=" + objdir, + ] + ) + args = [ + os.path.join(self.script_dir, "analyze.py"), + "dbs", + "--upto", + "dbs", + "-v", + "--buildcommand=" + buildscript, + ] + + return self.run_process(args=args, cwd=work_dir, pass_thru=True) + + @inherit_command_args("build") + @SubCommand("hazards", "compile", description=argparse.SUPPRESS) + @CommandArgument( + "--mozconfig", + default=None, + metavar="FILENAME", + help="Build with the given mozconfig.", + ) + @CommandArgument( + "--application", default="browser", help="Build the given application." + ) + @CommandArgument( + "--haz-objdir", + default=os.environ.get("HAZ_OBJDIR"), + help="Write object files to this directory.", + ) + def inner_compile(self, **kwargs): + """Build a source tree and gather analysis information while running + under the influence of the analysis collection server.""" + + env = os.environ + + # Check whether we are running underneath the manager (and therefore + # have a server to talk to). + if "XGILL_CONFIG" not in env: + raise Exception( + "no sixgill manager detected. `mach hazards compile` " + + "should only be run from `mach hazards gather`" + ) + + app = kwargs.pop("application") + default_mozconfig = "js/src/devtools/rootAnalysis/mozconfig.%s" % app + mozconfig_path = ( + kwargs.pop("mozconfig", None) or env.get("MOZCONFIG") or default_mozconfig + ) + mozconfig_path = os.path.join(self.topsrcdir, mozconfig_path) + + # Validate the mozconfig. + + # Require an explicit --enable-application=APP (even if you just + # want to build the default browser application.) + loader = MozconfigLoader(self.topsrcdir) + mozconfig = loader.read_mozconfig(mozconfig_path) + configure_args = mozconfig["configure_args"] + if "--enable-application=%s" % app not in configure_args: + raise Exception("mozconfig %s builds wrong project" % mozconfig_path) + if not any("--with-compiler-wrapper" in a for a in configure_args): + raise Exception("mozconfig must wrap compiles") + + # Communicate mozconfig to build subprocesses. + env["MOZCONFIG"] = os.path.join(self.topsrcdir, mozconfig_path) + + # hazard mozconfigs need to find binaries in .mozbuild + env["MOZBUILD_STATE_PATH"] = self.state_dir + + # Suppress the gathering of sources, to save disk space and memory. + env["XGILL_NO_SOURCE"] = "1" + + self.setup_env_for_tools(env) + + if "haz_objdir" in kwargs: + env["MOZ_OBJDIR"] = kwargs.pop("haz_objdir") + + return self._mach_context.commands.dispatch( + "build", self._mach_context, **kwargs + ) + + @SubCommand( + "hazards", "analyze", description="Analyzed gathered data for rooting hazards" + ) + @CommandArgument( + "--application", + default="browser", + help="Analyze the output for the given application.", + ) + @CommandArgument( + "--shell-objdir", + default=None, + help="objdir containing the optimized JS shell for running the analysis.", + ) + @CommandArgument( + "--work-dir", default=None, help="Directory for output and working files." + ) + def analyze(self, application, shell_objdir, work_dir): + """Analyzed gathered data for rooting hazards""" + + shell = self.ensure_shell(shell_objdir) + args = [ + os.path.join(self.script_dir, "analyze.py"), + "--js", + shell, + "gcTypes", + "-v", + ] + + self.setup_env_for_tools(os.environ) + os.environ["LD_LIBRARY_PATH"] += ":" + os.path.dirname(shell) + + work_dir = self.work_dir(application, work_dir) + return self.run_process(args=args, cwd=work_dir, pass_thru=True) + + @SubCommand( + "hazards", + "self-test", + description="Run a self-test to verify hazards are detected", + ) + @CommandArgument( + "--shell-objdir", + default=None, + help="objdir containing the optimized JS shell for running the analysis.", + ) + def self_test(self, shell_objdir): + """Analyzed gathered data for rooting hazards""" + shell = self.ensure_shell(shell_objdir) + args = [ + os.path.join(self.script_dir, "run-test.py"), + "-v", + "--js", + shell, + "--sixgill", + os.path.join(self.tools_dir, "sixgill"), + "--gccdir", + self.gcc_dir, + ] + + self.setup_env_for_tools(os.environ) + os.environ["LD_LIBRARY_PATH"] += ":" + os.path.dirname(shell) + return self.run_process(args=args, pass_thru=True) diff --git a/js/src/devtools/rootAnalysis/mozconfig.browser b/js/src/devtools/rootAnalysis/mozconfig.browser new file mode 100644 index 0000000000..60fcca048e --- /dev/null +++ b/js/src/devtools/rootAnalysis/mozconfig.browser @@ -0,0 +1,12 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +# This mozconfig is used when analyzing the source code of the Firefox browser +# for GC rooting hazards. See +# <https://wiki.mozilla.org/Javascript:SpiderMonkey:ExactStackRooting>. + +ac_add_options --enable-application=browser +ac_add_options --enable-js-shell + +. $topsrcdir/js/src/devtools/rootAnalysis/mozconfig.common diff --git a/js/src/devtools/rootAnalysis/mozconfig.common b/js/src/devtools/rootAnalysis/mozconfig.common new file mode 100644 index 0000000000..c68fb6a26c --- /dev/null +++ b/js/src/devtools/rootAnalysis/mozconfig.common @@ -0,0 +1,37 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +# Configuration shared between browser and shell builds. + +# The configuration options are chosen to compile the most code +# (--enable-debug, --enable-tests) in the trickiest way possible +# (--enable-optimize) to maximize the chance of seeing tricky static orderings. +ac_add_options --enable-debug +ac_add_options --enable-tests +ac_add_options --enable-optimize + +# Wrap all compiler invocations in order to enable the plugin and send +# information to a common database. +if [ -z "$AUTOMATION" ]; then + # Developer build: `mach hazards bootstrap` puts tools here: + TOOLS_DIR="$MOZBUILD_STATE_PATH/hazard-tools" +else + # Automation build: tools are downloaded from upstream tasks. + TOOLS_DIR="$MOZ_FETCHES_DIR" +fi +ac_add_options --with-compiler-wrapper="${TOOLS_DIR}"/sixgill/usr/libexec/sixgill/scripts/wrap_gcc/basecc + +# Stuff that gets in the way. +ac_add_options --without-ccache +ac_add_options --disable-replace-malloc + +# -Wattributes is very verbose due to attributes being ignored on template +# instantiations. +# +# -Wignored-attributes is very verbose due to attributes being +# ignored on template parameters. +ANALYSIS_EXTRA_CFLAGS="-Wno-attributes -Wno-ignored-attributes" +CFLAGS="$CFLAGS $ANALYSIS_EXTRA_CFLAGS" +CPPFLAGS="$CPPFLAGS $ANALYSIS_EXTRA_CFLAGS" +CXXFLAGS="$CXXFLAGS $ANALYSIS_EXTRA_CFLAGS" diff --git a/js/src/devtools/rootAnalysis/mozconfig.haz_shell b/js/src/devtools/rootAnalysis/mozconfig.haz_shell new file mode 100644 index 0000000000..76f9d36248 --- /dev/null +++ b/js/src/devtools/rootAnalysis/mozconfig.haz_shell @@ -0,0 +1,17 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +# This mozconfig is for compiling the JS shell that runs the static rooting +# hazard analysis. See +# <https://wiki.mozilla.org/Javascript:SpiderMonkey:ExactStackRooting>. + +ac_add_options --enable-ctypes +ac_add_options --enable-optimize +ac_add_options --disable-debug +ac_add_options --enable-application=js +ac_add_options --enable-nspr-build + +if [ -n "$AUTOMATION" ]; then + mk_add_options MOZ_OBJDIR="${HAZARD_SHELL_OBJDIR}" +fi diff --git a/js/src/devtools/rootAnalysis/mozconfig.js b/js/src/devtools/rootAnalysis/mozconfig.js new file mode 100644 index 0000000000..3699ed3fb0 --- /dev/null +++ b/js/src/devtools/rootAnalysis/mozconfig.js @@ -0,0 +1,16 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +# This mozconfig is used when analyzing the source code of the js/src tree for +# GC rooting hazards. See +# <https://wiki.mozilla.org/Javascript:SpiderMonkey:ExactStackRooting>. + +ac_add_options --enable-application=js + +# Also compile NSPR to see through its part of the control flow graph (not +# currently needed, but also helps with weird problems finding the right +# headers.) +ac_add_options --enable-nspr-build + +. $topsrcdir/js/src/devtools/rootAnalysis/mozconfig.common diff --git a/js/src/devtools/rootAnalysis/run-analysis.sh b/js/src/devtools/rootAnalysis/run-analysis.sh new file mode 100755 index 0000000000..157821cc92 --- /dev/null +++ b/js/src/devtools/rootAnalysis/run-analysis.sh @@ -0,0 +1,4 @@ +#!/bin/sh + +SRCDIR=$(cd $(dirname $0)/../../../..; pwd) +GECKO_PATH=$SRCDIR $SRCDIR/taskcluster/scripts/builder/build-haz-linux.sh $(pwd) "$@" diff --git a/js/src/devtools/rootAnalysis/run-test.py b/js/src/devtools/rootAnalysis/run-test.py new file mode 100755 index 0000000000..0ab2be4d8b --- /dev/null +++ b/js/src/devtools/rootAnalysis/run-test.py @@ -0,0 +1,124 @@ +#!/usr/bin/env python3 +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +from __future__ import print_function + +import os +import site +import subprocess +import argparse + +from glob import glob + +scriptdir = os.path.abspath(os.path.dirname(__file__)) +testdir = os.path.join(scriptdir, "t") + +site.addsitedir(testdir) +from testlib import Test, equal + +parser = argparse.ArgumentParser(description="run hazard analysis tests") +parser.add_argument( + "--js", default=os.environ.get("JS"), help="JS binary to run the tests with" +) +parser.add_argument( + "--sixgill", + default=os.environ.get("SIXGILL", os.path.join(testdir, "sixgill")), + help="Path to root of sixgill installation", +) +parser.add_argument( + "--sixgill-bin", + default=os.environ.get("SIXGILL_BIN"), + help="Path to sixgill binary dir", +) +parser.add_argument( + "--sixgill-plugin", + default=os.environ.get("SIXGILL_PLUGIN"), + help="Full path to sixgill gcc plugin", +) +parser.add_argument( + "--gccdir", default=os.environ.get("GCCDIR"), help="Path to GCC installation dir" +) +parser.add_argument("--cc", default=os.environ.get("CC"), help="Path to gcc") +parser.add_argument("--cxx", default=os.environ.get("CXX"), help="Path to g++") +parser.add_argument( + "--verbose", + "-v", + action="store_true", + help="Display verbose output, including commands executed", +) +parser.add_argument( + "tests", + nargs="*", + default=["sixgill-tree", "suppression", "hazards", "exceptions", "virtual"], + help="tests to run", +) + +cfg = parser.parse_args() + +if not cfg.js: + exit("Must specify JS binary through environment variable or --js option") +if not cfg.cc: + if cfg.gccdir: + cfg.cc = os.path.join(cfg.gccdir, "bin", "gcc") + else: + cfg.cc = "gcc" +if not cfg.cxx: + if cfg.gccdir: + cfg.cxx = os.path.join(cfg.gccdir, "bin", "g++") + else: + cfg.cxx = "g++" +if not cfg.sixgill_bin: + cfg.sixgill_bin = os.path.join(cfg.sixgill, "usr", "bin") +if not cfg.sixgill_plugin: + cfg.sixgill_plugin = os.path.join( + cfg.sixgill, "usr", "libexec", "sixgill", "gcc", "xgill.so" + ) + +subprocess.check_call( + [cfg.js, "-e", 'if (!getBuildConfiguration()["has-ctypes"]) quit(1)'] +) + + +def binpath(prog): + return os.path.join(cfg.sixgill_bin, prog) + + +def make_dir(dirname, exist_ok=True): + try: + os.mkdir(dirname) + except OSError as e: + if exist_ok and e.strerror == "File exists": + pass + else: + raise + + +outroot = os.path.join(testdir, "out") +make_dir(outroot) + +for name in cfg.tests: + name = os.path.basename(name) + indir = os.path.join(testdir, name) + outdir = os.path.join(outroot, name) + make_dir(outdir) + + test = Test(indir, outdir, cfg, verbose=cfg.verbose) + + os.chdir(outdir) + for xdb in glob("*.xdb"): + os.unlink(xdb) + print("START TEST {}".format(name), flush=True) + testpath = os.path.join(indir, "test.py") + testscript = open(testpath).read() + testcode = compile(testscript, testpath, "exec") + try: + exec(testcode, {"test": test, "equal": equal}) + except subprocess.CalledProcessError: + print("TEST-FAILED: %s" % name) + except AssertionError: + print("TEST-FAILED: %s" % name) + raise + else: + print("TEST-PASSED: %s" % name) diff --git a/js/src/devtools/rootAnalysis/run_complete b/js/src/devtools/rootAnalysis/run_complete new file mode 100755 index 0000000000..c9355267db --- /dev/null +++ b/js/src/devtools/rootAnalysis/run_complete @@ -0,0 +1,384 @@ +#!/usr/bin/perl + +# Sixgill: Static assertion checker for C/C++ programs. +# Copyright (C) 2009-2010 Stanford University +# Author: Brian Hackett +# +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <http://www.gnu.org/licenses/>. + +# do a complete run of the system from raw source to reports. this requires +# various run_monitor processes to be running in the background (maybe on other +# machines) and watching a shared poll_file for jobs. if the output directory +# for this script already exists then an incremental analysis will be performed +# and the reports will only reflect the changes since the earlier run. + +use strict; +use warnings; +use IO::Handle; +use File::Basename qw(basename dirname); +use Getopt::Long; +use Cwd; + +################################# +# environment specific settings # +################################# + +my $WORKDIR; +my $SIXGILL_BIN; + +# poll file shared with the run_monitor script. +my $poll_file; + +# root directory of the project. +my $build_dir; + +# directory containing gcc wrapper scripts. +my $wrap_dir; + +# optional file with annotations from the web interface. +my $ann_file = ""; + +# optional output directory to do a diff against. +my $old_dir = ""; + +# run in the foreground +my $foreground; + +my $builder = "make -j4"; + +my $suppress_logs; +GetOptions("build-root|b=s" => \$build_dir, + "poll-file=s" => \$poll_file, + "no-logs!" => \$suppress_logs, + "work-dir=s" => \$WORKDIR, + "sixgill-binaries|binaries|b=s" => \$SIXGILL_BIN, + "wrap-dir=s" => \$wrap_dir, + "annotations-file|annotations|a=s" => \$ann_file, + "old-dir|old=s" => \$old_dir, + "foreground!" => \$foreground, + "buildcommand=s" => \$builder, + ) + or die; + +if (not -d $build_dir) { + mkdir($build_dir); +} +if ($old_dir ne "" && not -d $old_dir) { + die "Old directory '$old_dir' does not exist\n"; +} + +$WORKDIR ||= "sixgill-work"; +mkdir($WORKDIR, 0755) if ! -d $WORKDIR; +$poll_file ||= "$WORKDIR/poll.file"; +$build_dir ||= "$WORKDIR/js-inbound-xgill"; + +if (!defined $SIXGILL_BIN) { + chomp(my $path = `which xmanager`); + if ($path) { + use File::Basename qw(dirname); + $SIXGILL_BIN = dirname($path); + } else { + die "Cannot find sixgill binaries. Use the -b option."; + } +} + +$wrap_dir ||= "$WORKDIR/xgill-inbound/wrap_gcc"; +$wrap_dir = "$SIXGILL_BIN/../scripts/wrap_gcc" if not (-e "$wrap_dir/basecc"); +die "Bad wrapper directory: $wrap_dir" if not (-e "$wrap_dir/basecc"); + +# code to clean the project from $build_dir. +sub clean_project { + system("make clean"); +} + +# code to build the project from $build_dir. +sub build_project { + return system($builder) >> 8; +} + +our %kill_on_exit; +END { + for my $pid (keys %kill_on_exit) { + kill($pid); + } +} + +# commands to start the various xgill binaries. timeouts can be specified +# for the backend analyses here, and a memory limit can be specified for +# xmanager if desired (and USE_COUNT_ALLOCATOR is defined in util/alloc.h). +my $xmanager = "$SIXGILL_BIN/xmanager"; +my $xsource = "$SIXGILL_BIN/xsource"; +my $xmemlocal = "$SIXGILL_BIN/xmemlocal -timeout=20"; +my $xinfer = "$SIXGILL_BIN/xinfer -timeout=60"; +my $xcheck = "$SIXGILL_BIN/xcheck -timeout=30"; + +# prefix directory to strip off source files. +my $prefix_dir = $build_dir; + +########################## +# general purpose script # +########################## + +# Prevent ccache from being used. I don't think this does any good. The problem +# I'm struggling with is that if autoconf.mk still has 'ccache gcc' in it, the +# builds fail in a mysterious way. +$ENV{CCACHE_COMPILERCHECK} = 'date +%s.%N'; +delete $ENV{CCACHE_PREFIX}; + +my $usage = "USAGE: run_complete result-dir\n"; +my $result_dir = shift or die $usage; + +if (not $foreground) { + my $pid = fork(); + if ($pid != 0) { + print "Forked, exiting...\n"; + exit(0); + } +} + +# if the result directory does not already exist, mark for a clean build. +my $do_clean = 0; +if (not (-d $result_dir)) { + $do_clean = 1; + mkdir $result_dir; +} + +if (!$suppress_logs) { + my $log_file = "$result_dir/complete.log"; + open(OUT, ">>", $log_file) or die "append to $log_file: $!"; + OUT->autoflush(1); # don't buffer writes to the main log. + + # redirect stdout and stderr to the log. + STDOUT->fdopen(\*OUT, "w"); + STDERR->fdopen(\*OUT, "w"); +} + +# pids to wait on before exiting. these are collating worker output. +my @waitpids; + +chdir $result_dir; + +# to do a partial run, comment out the commands here you don't want to do. + +my $status = run_build(); + +# end of run commands. + +for my $pid (@waitpids) { + waitpid($pid, 0); + $status ||= $? >> 8; +} + +print "Exiting run_complete with status $status\n"; +exit $status; + +# get the IP address which a freshly created manager is listening on. +sub get_manager_address +{ + my $log_file = shift or die; + + # give the manager one second to start, any longer and something's broken. + sleep(1); + + my $log_data = `cat $log_file`; + my ($port) = $log_data =~ /Listening on ([\.\:0-9]*)/ + or die "no manager found"; + print OUT "Connecting to manager on port $port\n" unless $suppress_logs; + print "Connecting to manager on port $port.\n"; + return $1; +} + +sub logging_suffix { + my ($show_logs, $log_file) = @_; + return $show_logs ? "2>&1 | tee $log_file" + : "> $log_file 2>&1"; +} + +sub run_build +{ + print "build started: "; + print scalar(localtime()); + print "\n"; + + # fork off a process to run the build. + defined(my $pid = fork) or die; + + # log file for the manager. + my $manager_log_file = "$result_dir/build_manager.log"; + + if (!$pid) { + # this is the child process, fork another process to run a manager. + defined(my $pid = fork) or die; + my $logging = logging_suffix($suppress_logs, $manager_log_file); + exec("$xmanager -terminate-on-assert $logging") if (!$pid); + $kill_on_exit{$pid} = 1; + + if (!$suppress_logs) { + # open new streams to redirect stdout and stderr. + open(LOGOUT, "> $result_dir/build.log"); + open(LOGERR, "> $result_dir/build_err.log"); + STDOUT->fdopen(\*LOGOUT, "w"); + STDERR->fdopen(\*LOGERR, "w"); + } + + my $address = get_manager_address($manager_log_file); + + # write the configuration file for the wrapper script. + my $config_file = "$WORKDIR/xgill.config"; + open(CONFIG, ">", $config_file) or die "create $config_file: $!"; + print CONFIG "$prefix_dir\n"; + print CONFIG Cwd::abs_path("$result_dir/build_xgill.log")."\n"; + print CONFIG "$address\n"; + my @extra = ("-fplugin-arg-xgill-mangle=1"); + push(@extra, "-fplugin-arg-xgill-annfile=$ann_file") + if ($ann_file ne "" && -e $ann_file); + print CONFIG join(" ", @extra) . "\n"; + close(CONFIG); + + # Tell the wrapper where to find the config + $ENV{"XGILL_CONFIG"} = Cwd::abs_path($config_file); + + # If overriding $CC, use GCCDIR to tell the wrapper scripts where the + # real compiler is. If $CC is not set, then the wrapper script will + # search $PATH anyway. + if (exists $ENV{CC}) { + $ENV{GCCDIR} = dirname($ENV{CC}); + } + + # Force the wrapper scripts to be run in place of the compiler during + # whatever build process we use. + $ENV{CC} = "$wrap_dir/" . basename($ENV{CC} // "gcc"); + $ENV{CXX} = "$wrap_dir/" . basename($ENV{CXX} // "g++"); + + # do the build, cleaning if necessary. + chdir $build_dir; + clean_project() if ($do_clean); + my $exit_status = build_project(); + + # signal the manager that it's over. + system("$xsource -remote=$address -end-manager"); + + # wait for the manager to clean up and terminate. + print "Waiting for manager to finish (build status $exit_status)...\n"; + waitpid($pid, 0); + my $manager_status = $?; + delete $kill_on_exit{$pid}; + + # build is finished, the complete run can resume. + # return value only useful if --foreground + print "Exiting with status " . ($manager_status || $exit_status) . "\n"; + exit($manager_status || $exit_status); + } + + # this is the complete process, wait for the build to finish. + waitpid($pid, 0); + my $status = $? >> 8; + print "build finished (status $status): "; + print scalar(localtime()); + print "\n"; + + return $status; +} + +sub run_pass +{ + my ($name, $command) = @_; + my $log_file = "$result_dir/manager.$name.log"; + + # extra commands to pass to the manager. + my $manager_extra = ""; + $manager_extra .= "-modset-wait=10" if ($name eq "xmemlocal"); + + # fork off a manager process for the analysis. + defined(my $pid = fork) or die; + my $logging = logging_suffix($suppress_logs, $log_file); + exec("$xmanager $manager_extra $logging") if (!$pid); + + my $address = get_manager_address($log_file); + + # write the poll file for this pass. + if (! -d dirname($poll_file)) { + system("mkdir", "-p", dirname($poll_file)); + } + open(POLL, "> $poll_file"); + print POLL "$command\n"; + print POLL "$result_dir/$name\n"; + print POLL "$address\n"; + close(POLL); + + print "$name started: "; + print scalar(localtime()); + print "\n"; + + waitpid($pid, 0); + unlink($poll_file); + + print "$name finished: "; + print scalar(localtime()); + print "\n"; + + # collate the worker's output into a single file. make this asynchronous + # so we can wait a bit and make sure we get all worker output. + defined($pid = fork) or die; + + if (!$pid) { + sleep(20); + exec("cat $name.*.log > $name.log"); + } + + push(@waitpids, $pid); +} + +# the names of all directories containing reports to archive. +my $indexes; + +sub run_index +{ + my ($name, $kind) = @_; + + return if (not (-e "report_$kind.xdb")); + + print "$name started: "; + print scalar(localtime()); + print "\n"; + + # make an index for the report diff if applicable. + if ($old_dir ne "") { + system("make_index $kind $old_dir > $name.diff.log"); + system("mv $kind diff_$kind"); + $indexes .= " diff_$kind"; + } + + # make an index for the full set of reports. + system("make_index $kind > $name.log"); + $indexes .= " $kind"; + + print "$name finished: "; + print scalar(localtime()); + print "\n"; +} + +sub archive_indexes +{ + print "archive started: "; + print scalar(localtime()); + print "\n"; + + system("tar -czf reports.tgz $indexes"); + system("rm -rf $indexes"); + + print "archive finished: "; + print scalar(localtime()); + print "\n"; +} diff --git a/js/src/devtools/rootAnalysis/t/exceptions/source.cpp b/js/src/devtools/rootAnalysis/t/exceptions/source.cpp new file mode 100644 index 0000000000..70e6ff9841 --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/exceptions/source.cpp @@ -0,0 +1,54 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#define ANNOTATE(property) __attribute__((annotate(property))) + +struct Cell { + int f; +} ANNOTATE("GC Thing"); + +extern void GC() ANNOTATE("GC Call"); + +void GC() { + // If the implementation is too trivial, the function body won't be emitted at + // all. + asm(""); +} + +class RAII_GC { + public: + RAII_GC() {} + ~RAII_GC() { GC(); } +}; + +// ~AutoSomething calls GC because of the RAII_GC field. The constructor, +// though, should *not* GC -- unless it throws an exception. Which is not +// possible when compiled with -fno-exceptions. This test will try it both +// ways. +class AutoSomething { + RAII_GC gc; + + public: + AutoSomething() : gc() { + asm(""); // Ooh, scary, this might throw an exception + } + ~AutoSomething() { asm(""); } +}; + +extern Cell* getcell(); + +extern void usevar(Cell* cell); + +void f() { + Cell* thing = getcell(); // Live range starts here + + // When compiling with -fexceptions, there should be a hazard below. With + // -fno-exceptions, there should not be one. We will check both. + { + AutoSomething smth; // Constructor can GC only if exceptions are enabled + usevar(thing); // Live range ends here + } // In particular, 'thing' is dead at the destructor, so no hazard +} diff --git a/js/src/devtools/rootAnalysis/t/exceptions/test.py b/js/src/devtools/rootAnalysis/t/exceptions/test.py new file mode 100644 index 0000000000..a40753d87a --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/exceptions/test.py @@ -0,0 +1,21 @@ +# flake8: noqa: F821 + +test.compile("source.cpp", "-fno-exceptions") +test.run_analysis_script("gcTypes") + +hazards = test.load_hazards() +assert len(hazards) == 0 + +# If we compile with exceptions, then there *should* be a hazard because +# AutoSomething::AutoSomething might throw an exception, which would cause the +# partially-constructed value to be torn down, which will call ~RAII_GC. + +test.compile("source.cpp", "-fexceptions") +test.run_analysis_script("gcTypes") + +hazards = test.load_hazards() +assert len(hazards) == 1 +hazard = hazards[0] +assert hazard.function == "void f()" +assert hazard.variable == "thing" +assert "AutoSomething::AutoSomething" in hazard.GCFunction diff --git a/js/src/devtools/rootAnalysis/t/hazards/source.cpp b/js/src/devtools/rootAnalysis/t/hazards/source.cpp new file mode 100644 index 0000000000..69ed3d4100 --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/hazards/source.cpp @@ -0,0 +1,326 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <utility> + +#define ANNOTATE(property) __attribute__((annotate(property))) + +struct Cell { + int f; +} ANNOTATE("GC Thing"); + +template <typename T, typename U> +struct UntypedContainer { + char data[sizeof(T) + sizeof(U)]; +} ANNOTATE("moz_inherit_type_annotations_from_template_args"); + +struct RootedCell { + RootedCell(Cell*) {} +} ANNOTATE("Rooted Pointer"); + +class AutoSuppressGC_Base { + public: + AutoSuppressGC_Base() {} + ~AutoSuppressGC_Base() {} +} ANNOTATE("Suppress GC"); + +class AutoSuppressGC_Child : public AutoSuppressGC_Base { + public: + AutoSuppressGC_Child() : AutoSuppressGC_Base() {} +}; + +class AutoSuppressGC { + AutoSuppressGC_Child helpImBeingSuppressed; + + public: + AutoSuppressGC() {} +}; + +extern void GC() ANNOTATE("GC Call"); +extern void invisible(); + +void GC() { + // If the implementation is too trivial, the function body won't be emitted at + // all. + asm(""); + invisible(); +} + +extern void usecell(Cell*); + +void suppressedFunction() { + GC(); // Calls GC, but is always called within AutoSuppressGC +} + +void halfSuppressedFunction() { + GC(); // Calls GC, but is sometimes called within AutoSuppressGC +} + +void unsuppressedFunction() { + GC(); // Calls GC, never within AutoSuppressGC +} + +volatile static int x = 3; +volatile static int* xp = &x; +struct GCInDestructor { + ~GCInDestructor() { + invisible(); + asm(""); + *xp = 4; + GC(); + } +}; + +template <typename T> +void usecontainer(T* value) { + if (value) asm(""); +} + +Cell* cell() { + static Cell c; + return &c; +} + +Cell* f() { + GCInDestructor kaboom; + + Cell* cell1 = cell(); + Cell* cell2 = cell(); + Cell* cell3 = cell(); + Cell* cell4 = cell(); + { + AutoSuppressGC nogc; + suppressedFunction(); + halfSuppressedFunction(); + } + usecell(cell1); + halfSuppressedFunction(); + usecell(cell2); + unsuppressedFunction(); + { + // Old bug: it would look from the first AutoSuppressGC constructor it + // found to the last destructor. This statement *should* have no effect. + AutoSuppressGC nogc; + } + usecell(cell3); + Cell* cell5 = cell(); + usecell(cell5); + + { + // Templatized container that inherits attributes from Cell*, should + // report a hazard. + UntypedContainer<int, Cell*> container1; + usecontainer(&container1); + GC(); + usecontainer(&container1); + } + + { + // As above, but with a non-GC type. + UntypedContainer<int, double> container2; + usecontainer(&container2); + GC(); + usecontainer(&container2); + } + + // Hazard in return value due to ~GCInDestructor + Cell* cell6 = cell(); + return cell6; +} + +Cell* copy_and_gc(Cell* src) { + GC(); + return reinterpret_cast<Cell*>(88); +} + +void use(Cell* cell) { + static int x = 0; + if (cell) x++; +} + +struct CellContainer { + Cell* cell; + CellContainer() { asm(""); } +}; + +void loopy() { + Cell cell; + + // No hazard: haz1 is not live during call to copy_and_gc. + Cell* haz1; + for (int i = 0; i < 10; i++) { + haz1 = copy_and_gc(haz1); + } + + // No hazard: haz2 is live up to just before the GC, and starting at the + // next statement after it, but not across the GC. + Cell* haz2 = &cell; + for (int j = 0; j < 10; j++) { + use(haz2); + GC(); + haz2 = &cell; + } + + // Hazard: haz3 is live from the final statement in one iteration, across + // the GC in the next, to the use in the 2nd statement. + Cell* haz3; + for (int k = 0; k < 10; k++) { + GC(); + use(haz3); + haz3 = &cell; + } + + // Hazard: haz4 is live across a GC hidden in a loop. + Cell* haz4 = &cell; + for (int i2 = 0; i2 < 10; i2++) { + GC(); + } + use(haz4); + + // Hazard: haz5 is live from within a loop across a GC. + Cell* haz5; + for (int i3 = 0; i3 < 10; i3++) { + haz5 = &cell; + } + GC(); + use(haz5); + + // No hazard: similar to the haz3 case, but verifying that we do not get + // into an infinite loop. + Cell* haz6; + for (int i4 = 0; i4 < 10; i4++) { + GC(); + haz6 = &cell; + } + + // No hazard: haz7 is constructed within the body, so it can't make a + // hazard across iterations. Note that this requires CellContainer to have + // a constructor, because otherwise the analysis doesn't see where + // variables are declared. (With the constructor, it knows that + // construction of haz7 obliterates any previous value it might have had. + // Not that that's possible given its scope, but the analysis doesn't get + // that information.) + for (int i5 = 0; i5 < 10; i5++) { + GC(); + CellContainer haz7; + use(haz7.cell); + haz7.cell = &cell; + } + + // Hazard: make sure we *can* see hazards across iterations involving + // CellContainer; + CellContainer haz8; + for (int i6 = 0; i6 < 10; i6++) { + GC(); + use(haz8.cell); + haz8.cell = &cell; + } +} + +namespace mozilla { +template <typename T> +class UniquePtr { + T* val; + + public: + UniquePtr() : val(nullptr) { asm(""); } + UniquePtr(T* p) : val(p) {} + UniquePtr(UniquePtr<T>&& u) : val(u.val) { u.val = nullptr; } + ~UniquePtr() { use(val); } + T* get() { return val; } + void reset() { val = nullptr; } +} ANNOTATE("moz_inherit_type_annotations_from_template_args"); +} // namespace mozilla + +extern void consume(mozilla::UniquePtr<Cell> uptr); + +void safevals() { + Cell cell; + + // Simple hazard. + Cell* unsafe1 = &cell; + GC(); + use(unsafe1); + + // Safe because it's known to be nullptr. + Cell* safe2 = &cell; + safe2 = nullptr; + GC(); + use(safe2); + + // Unsafe because it may not be nullptr. + Cell* unsafe3 = &cell; + if (reinterpret_cast<long>(&cell) & 0x100) { + unsafe3 = nullptr; + } + GC(); + use(unsafe3); + + // Unsafe because it's not nullptr anymore. + Cell* unsafe3b = &cell; + unsafe3b = nullptr; + unsafe3b = &cell; + GC(); + use(unsafe3b); + + // Hazard involving UniquePtr. + { + mozilla::UniquePtr<Cell> unsafe4(&cell); + GC(); + // Destructor uses unsafe4. + } + + // reset() to safe value before the GC. + { + mozilla::UniquePtr<Cell> safe5(&cell); + safe5.reset(); + GC(); + } + + // reset() to safe value after the GC. + { + mozilla::UniquePtr<Cell> safe6(&cell); + GC(); + safe6.reset(); + } + + // reset() to safe value after the GC -- but we've already used it, so it's + // too late. + { + mozilla::UniquePtr<Cell> unsafe7(&cell); + GC(); + use(unsafe7.get()); + unsafe7.reset(); + } + + // initialized to safe value. + { + mozilla::UniquePtr<Cell> safe8; + GC(); + } + + // passed to a function that takes ownership before GC. + { + mozilla::UniquePtr<Cell> safe9(&cell); + consume(std::move(safe9)); + GC(); + } + + // passed to a function that takes ownership after GC. + { + mozilla::UniquePtr<Cell> unsafe10(&cell); + GC(); + consume(std::move(unsafe10)); + } +} + +// Make sure `this` is live at the beginning of a function. +class Subcell : public Cell { + int method() { + GC(); + return f; // this->f + } +}; diff --git a/js/src/devtools/rootAnalysis/t/hazards/test.py b/js/src/devtools/rootAnalysis/t/hazards/test.py new file mode 100644 index 0000000000..8d3df8186b --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/hazards/test.py @@ -0,0 +1,83 @@ +# flake8: noqa: F821 + +from collections import defaultdict + +test.compile("source.cpp") +test.run_analysis_script("gcTypes") + +# gcFunctions should be the inverse, but we get to rely on unmangled names here. +gcFunctions = test.load_gcFunctions() +print(gcFunctions) +assert "void GC()" in gcFunctions +assert "void suppressedFunction()" not in gcFunctions +assert "void halfSuppressedFunction()" in gcFunctions +assert "void unsuppressedFunction()" in gcFunctions +assert "int32 Subcell::method()" in gcFunctions +assert "Cell* f()" in gcFunctions + +hazards = test.load_hazards() +hazmap = {haz.variable: haz for haz in hazards} +assert "cell1" not in hazmap +assert "cell2" in hazmap +assert "cell3" in hazmap +assert "cell4" not in hazmap +assert "cell5" not in hazmap +assert "cell6" not in hazmap +assert "<returnvalue>" in hazmap +assert "this" in hazmap + +# All hazards should be in f(), loopy(), safevals(), and method() +assert hazmap["cell2"].function == "Cell* f()" +print(len(set(haz.function for haz in hazards))) +assert len(set(haz.function for haz in hazards)) == 4 + +# Check that the correct GC call is reported for each hazard. (cell3 has a +# hazard from two different GC calls; it doesn't really matter which is +# reported.) +assert hazmap["cell2"].GCFunction == "void halfSuppressedFunction()" +assert hazmap["cell3"].GCFunction in ( + "void halfSuppressedFunction()", + "void unsuppressedFunction()", +) +assert hazmap["<returnvalue>"].GCFunction == "void GCInDestructor::~GCInDestructor()" + +assert "container1" in hazmap +assert "container2" not in hazmap + +# Type names are handy to have in the report. +assert hazmap["cell2"].type == "Cell*" +assert hazmap["<returnvalue>"].type == "Cell*" +assert hazmap["this"].type == "Subcell*" + +# loopy hazards. See comments in source. +assert "haz1" not in hazmap +assert "haz2" not in hazmap +assert "haz3" in hazmap +assert "haz4" in hazmap +assert "haz5" in hazmap +assert "haz6" not in hazmap +assert "haz7" not in hazmap +assert "haz8" in hazmap + +# safevals hazards. See comments in source. +assert "unsafe1" in hazmap +assert "safe2" not in hazmap +assert "unsafe3" in hazmap +assert "unsafe3b" in hazmap +assert "unsafe4" in hazmap +assert "safe5" not in hazmap +assert "safe6" not in hazmap +assert "unsafe7" in hazmap +assert "safe8" not in hazmap +assert "safe9" not in hazmap +assert "safe10" not in hazmap + +# method hazard. + +byfunc = defaultdict(lambda: defaultdict(dict)) +for haz in hazards: + byfunc[haz.function][haz.variable] = haz + +methhaz = byfunc["int32 Subcell::method()"] +assert "this" in methhaz +assert methhaz["this"].type == "Subcell*" diff --git a/js/src/devtools/rootAnalysis/t/sixgill-tree/source.cpp b/js/src/devtools/rootAnalysis/t/sixgill-tree/source.cpp new file mode 100644 index 0000000000..149d77b03a --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/sixgill-tree/source.cpp @@ -0,0 +1,76 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#define ANNOTATE(property) __attribute__((annotate(property))) + +namespace js { +namespace gc { +struct Cell { + int f; +} ANNOTATE("GC Thing"); +} // namespace gc +} // namespace js + +struct Bogon {}; + +struct JustACell : public js::gc::Cell { + bool iHaveNoDataMembers() { return true; } +}; + +struct JSObject : public js::gc::Cell, public Bogon { + int g; +}; + +struct SpecialObject : public JSObject { + int z; +}; + +struct ErrorResult { + bool hasObj; + JSObject* obj; + void trace() {} +} ANNOTATE("Suppressed GC Pointer"); + +struct OkContainer { + ErrorResult res; + bool happy; +}; + +struct UnrootedPointer { + JSObject* obj; +}; + +template <typename T> +class Rooted { + T data; +} ANNOTATE("Rooted Pointer"); + +extern void js_GC() ANNOTATE("GC Call") ANNOTATE("Slow"); + +void js_GC() {} + +void root_arg(JSObject* obj, JSObject* random) { + // Use all these types so they get included in the output. + SpecialObject so; + UnrootedPointer up; + Bogon b; + OkContainer okc; + Rooted<JSObject*> ro; + Rooted<SpecialObject*> rso; + + obj = random; + + JSObject* other1 = obj; + js_GC(); + + float MARKER1 = 0; + JSObject* other2 = obj; + other1->f = 1; + other2->f = -1; + + unsigned int u1 = 1; + unsigned int u2 = -1; +} diff --git a/js/src/devtools/rootAnalysis/t/sixgill-tree/test.py b/js/src/devtools/rootAnalysis/t/sixgill-tree/test.py new file mode 100644 index 0000000000..5e99fff908 --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/sixgill-tree/test.py @@ -0,0 +1,63 @@ +# flake8: noqa: F821 +import re + +test.compile("source.cpp") +test.computeGCTypes() +body = test.process_body(test.load_db_entry("src_body", re.compile(r"root_arg"))[0]) + +# Rendering positive and negative integers +marker1 = body.assignment_line("MARKER1") +equal(body.edge_from_line(marker1 + 2)["Exp"][1]["String"], "1") +equal(body.edge_from_line(marker1 + 3)["Exp"][1]["String"], "-1") + +equal(body.edge_from_point(body.assignment_point("u1"))["Exp"][1]["String"], "1") +equal( + body.edge_from_point(body.assignment_point("u2"))["Exp"][1]["String"], "4294967295" +) + +assert "obj" in body["Variables"] +assert "random" in body["Variables"] +assert "other1" in body["Variables"] +assert "other2" in body["Variables"] + +# Test function annotations +js_GC = test.process_body(test.load_db_entry("src_body", re.compile(r"js_GC"))[0]) +annotations = js_GC["Variables"]["void js_GC()"]["Annotation"] +assert annotations +found_call_annotate = False +for annotation in annotations: + (annType, value) = annotation["Name"] + if annType == "annotate" and value == "GC Call": + found_call_annotate = True +assert found_call_annotate + +# Test type annotations + +# js::gc::Cell first +cell = test.load_db_entry("src_comp", "js::gc::Cell")[0] +assert cell["Kind"] == "Struct" +annotations = cell["Annotation"] +assert len(annotations) == 1 +(tag, value) = annotations[0]["Name"] +assert tag == "annotate" +assert value == "GC Thing" + +# Check JSObject inheritance. +JSObject = test.load_db_entry("src_comp", "JSObject")[0] +bases = [b["Base"] for b in JSObject["CSUBaseClass"]] +assert "js::gc::Cell" in bases +assert "Bogon" in bases +assert len(bases) == 2 + +# Check type analysis +gctypes = test.load_gcTypes() +assert "js::gc::Cell" in gctypes["GCThings"] +assert "JustACell" in gctypes["GCThings"] +assert "JSObject" in gctypes["GCThings"] +assert "SpecialObject" in gctypes["GCThings"] +assert "UnrootedPointer" in gctypes["GCPointers"] +assert "Bogon" not in gctypes["GCThings"] +assert "Bogon" not in gctypes["GCPointers"] +assert "ErrorResult" not in gctypes["GCPointers"] +assert "OkContainer" not in gctypes["GCPointers"] +assert "class Rooted<JSObject*>" not in gctypes["GCPointers"] diff --git a/js/src/devtools/rootAnalysis/t/sixgill.py b/js/src/devtools/rootAnalysis/t/sixgill.py new file mode 100644 index 0000000000..0b8c2c7073 --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/sixgill.py @@ -0,0 +1,70 @@ +#!/usr/bin/env python +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +from collections import defaultdict + +# Simplified version of the body info. + + +class Body(dict): + def __init__(self, body): + self["BlockIdKind"] = body["BlockId"]["Kind"] + if "Variable" in body["BlockId"]: + self["BlockName"] = body["BlockId"]["Variable"]["Name"][0].split("$")[-1] + loc = body["Location"] + self["LineRange"] = (loc[0]["Line"], loc[1]["Line"]) + self["Filename"] = loc[0]["CacheString"] + self["Edges"] = body.get("PEdge", []) + self["Points"] = { + i: p["Location"]["Line"] for i, p in enumerate(body["PPoint"], 1) + } + self["Index"] = body["Index"] + self["Variables"] = { + x["Variable"]["Name"][0].split("$")[-1]: x["Type"] + for x in body["DefineVariable"] + } + + # Indexes + self["Line2Points"] = defaultdict(list) + for point, line in self["Points"].items(): + self["Line2Points"][line].append(point) + self["SrcPoint2Edges"] = defaultdict(list) + for edge in self["Edges"]: + src, dst = edge["Index"] + self["SrcPoint2Edges"][src].append(edge) + self["Line2Edges"] = defaultdict(list) + for (src, edges) in self["SrcPoint2Edges"].items(): + line = self["Points"][src] + self["Line2Edges"][line].extend(edges) + + def edges_from_line(self, line): + return self["Line2Edges"][line] + + def edge_from_line(self, line): + edges = self.edges_from_line(line) + assert len(edges) == 1 + return edges[0] + + def edges_from_point(self, point): + return self["SrcPoint2Edges"][point] + + def edge_from_point(self, point): + edges = self.edges_from_point(point) + assert len(edges) == 1 + return edges[0] + + def assignment_point(self, varname): + for edge in self["Edges"]: + if edge["Kind"] != "Assign": + continue + dst = edge["Exp"][0] + if dst["Kind"] != "Var": + continue + if dst["Variable"]["Name"][0] == varname: + return edge["Index"][0] + raise Exception("assignment to variable %s not found" % varname) + + def assignment_line(self, varname): + return self["Points"][self.assignment_point(varname)] diff --git a/js/src/devtools/rootAnalysis/t/suppression/source.cpp b/js/src/devtools/rootAnalysis/t/suppression/source.cpp new file mode 100644 index 0000000000..56e458bdaa --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/suppression/source.cpp @@ -0,0 +1,72 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#define ANNOTATE(property) __attribute__((annotate(property))) + +struct Cell { + int f; +} ANNOTATE("GC Thing"); + +class AutoSuppressGC_Base { + public: + AutoSuppressGC_Base() {} + ~AutoSuppressGC_Base() {} +} ANNOTATE("Suppress GC"); + +class AutoSuppressGC_Child : public AutoSuppressGC_Base { + public: + AutoSuppressGC_Child() : AutoSuppressGC_Base() {} +}; + +class AutoSuppressGC { + AutoSuppressGC_Child helpImBeingSuppressed; + + public: + AutoSuppressGC() {} +}; + +extern void GC() ANNOTATE("GC Call"); + +void GC() { + // If the implementation is too trivial, the function body won't be emitted at + // all. + asm(""); +} + +extern void foo(Cell*); + +void suppressedFunction() { + GC(); // Calls GC, but is always called within AutoSuppressGC +} + +void halfSuppressedFunction() { + GC(); // Calls GC, but is sometimes called within AutoSuppressGC +} + +void unsuppressedFunction() { + GC(); // Calls GC, never within AutoSuppressGC +} + +void f() { + Cell* cell1 = nullptr; + Cell* cell2 = nullptr; + Cell* cell3 = nullptr; + { + AutoSuppressGC nogc; + suppressedFunction(); + halfSuppressedFunction(); + } + foo(cell1); + halfSuppressedFunction(); + foo(cell2); + unsuppressedFunction(); + { + // Old bug: it would look from the first AutoSuppressGC constructor it + // found to the last destructor. This statement *should* have no effect. + AutoSuppressGC nogc; + } + foo(cell3); +} diff --git a/js/src/devtools/rootAnalysis/t/suppression/test.py b/js/src/devtools/rootAnalysis/t/suppression/test.py new file mode 100644 index 0000000000..b1a1c2f21f --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/suppression/test.py @@ -0,0 +1,20 @@ +# flake8: noqa: F821 +test.compile("source.cpp") +test.run_analysis_script("gcTypes", upto="gcFunctions") + +# The suppressions file uses mangled names. +suppressed = test.load_suppressed_functions() + +# Only one of these is fully suppressed (ie, *always* called within the scope +# of an AutoSuppressGC). +assert len(list(filter(lambda f: "suppressedFunction" in f, suppressed))) == 1 +assert len(list(filter(lambda f: "halfSuppressedFunction" in f, suppressed))) == 0 +assert len(list(filter(lambda f: "unsuppressedFunction" in f, suppressed))) == 0 + +# gcFunctions should be the inverse, but we get to rely on unmangled names here. +gcFunctions = test.load_gcFunctions() +assert "void GC()" in gcFunctions +assert "void suppressedFunction()" not in gcFunctions +assert "void halfSuppressedFunction()" in gcFunctions +assert "void unsuppressedFunction()" in gcFunctions +assert "void f()" in gcFunctions diff --git a/js/src/devtools/rootAnalysis/t/testlib.py b/js/src/devtools/rootAnalysis/t/testlib.py new file mode 100644 index 0000000000..d187164d84 --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/testlib.py @@ -0,0 +1,231 @@ +import json +import os +import re +import subprocess + +from sixgill import Body +from collections import defaultdict, namedtuple + +scriptdir = os.path.abspath(os.path.join(os.path.dirname(__file__), "..")) + +HazardSummary = namedtuple( + "HazardSummary", ["function", "variable", "type", "GCFunction", "location"] +) + +Callgraph = namedtuple( + "Callgraph", + [ + "functionNames", + "nameToId", + "mangledToUnmangled", + "unmangledToMangled", + "calleesOf", + "callersOf", + "tags", + "calleeGraph", + "callerGraph", + ], +) + + +def equal(got, expected): + if got != expected: + print("Got '%s', expected '%s'" % (got, expected)) + + +def extract_unmangled(func): + return func.split("$")[-1] + + +class Test(object): + def __init__(self, indir, outdir, cfg, verbose=0): + self.indir = indir + self.outdir = outdir + self.cfg = cfg + self.verbose = verbose + + def infile(self, path): + return os.path.join(self.indir, path) + + def binpath(self, prog): + return os.path.join(self.cfg.sixgill_bin, prog) + + def compile(self, source, options=""): + env = os.environ + env["CCACHE_DISABLE"] = "1" + cmd = "{CXX} -c {source} -O3 -std=c++11 -fplugin={sixgill} -fplugin-arg-xgill-mangle=1 {options}".format( # NOQA: E501 + source=self.infile(source), + CXX=self.cfg.cxx, + sixgill=self.cfg.sixgill_plugin, + options=options, + ) + if self.cfg.verbose: + print("Running %s" % cmd) + subprocess.check_call(["sh", "-c", cmd]) + + def load_db_entry(self, dbname, pattern): + """Look up an entry from an XDB database file, 'pattern' may be an exact + matching string, or an re pattern object matching a single entry.""" + + if hasattr(pattern, "match"): + output = subprocess.check_output( + [self.binpath("xdbkeys"), dbname + ".xdb"], universal_newlines=True + ) + matches = list(filter(lambda _: re.search(pattern, _), output.splitlines())) + if len(matches) == 0: + raise Exception("entry not found") + if len(matches) > 1: + raise Exception("multiple entries found") + pattern = matches[0] + + output = subprocess.check_output( + [self.binpath("xdbfind"), "-json", dbname + ".xdb", pattern], + universal_newlines=True, + ) + return json.loads(output) + + def run_analysis_script(self, phase, upto=None): + open("defaults.py", "w").write( + """\ +analysis_scriptdir = '{scriptdir}' +sixgill_bin = '{bindir}' +""".format( + scriptdir=scriptdir, bindir=self.cfg.sixgill_bin + ) + ) + cmd = [ + os.path.join(scriptdir, "analyze.py"), + "-v" if self.verbose else "-q", + phase, + ] + if upto: + cmd += ["--upto", upto] + cmd.append("--source=%s" % self.indir) + cmd.append("--objdir=%s" % self.outdir) + cmd.append("--js=%s" % self.cfg.js) + if self.cfg.verbose: + cmd.append("--verbose") + print("Running " + " ".join(cmd)) + subprocess.check_call(cmd) + + def computeGCTypes(self): + self.run_analysis_script("gcTypes", upto="gcTypes") + + def computeHazards(self): + self.run_analysis_script("gcTypes") + + def load_text_file(self, filename, extract=lambda l: l): + fullpath = os.path.join(self.outdir, filename) + values = (extract(line.strip()) for line in open(fullpath, "r")) + return list(filter(lambda _: _ is not None, values)) + + def load_suppressed_functions(self): + return set( + self.load_text_file( + "limitedFunctions.lst", extract=lambda l: l.split(" ")[1] + ) + ) + + def load_gcTypes(self): + def grab_type(line): + m = re.match(r"^(GC\w+): (.*)", line) + if m: + return (m.group(1) + "s", m.group(2)) + return None + + gctypes = defaultdict(list) + for collection, typename in self.load_text_file( + "gcTypes.txt", extract=grab_type + ): + gctypes[collection].append(typename) + return gctypes + + def load_typeInfo(self, filename="typeInfo.txt"): + with open(os.path.join(self.outdir, filename)) as fh: + return json.load(fh) + + def load_gcFunctions(self): + return self.load_text_file("gcFunctions.lst", extract=extract_unmangled) + + def load_callgraph(self): + data = Callgraph( + functionNames=["dummy"], + nameToId={}, + mangledToUnmangled={}, + unmangledToMangled={}, + calleesOf=defaultdict(list), + callersOf=defaultdict(list), + tags=defaultdict(set), + calleeGraph=defaultdict(dict), + callerGraph=defaultdict(dict), + ) + + def lookup(id): + mangled = data.functionNames[int(id)] + return data.mangledToUnmangled.get(mangled, mangled) + + def add_call(caller, callee, limit): + data.calleesOf[caller].append(callee) + data.callersOf[callee].append(caller) + data.calleeGraph[caller][callee] = True + data.callerGraph[callee][caller] = True + + def process(line): + if line.startswith("#"): + name = line.split(" ", 1)[1] + data.nameToId[name] = len(data.functionNames) + data.functionNames.append(name) + return + + if line.startswith("="): + m = re.match(r"^= (\d+) (.*)", line) + mangled = data.functionNames[int(m.group(1))] + unmangled = m.group(2) + data.nameToId[unmangled] = id + data.mangledToUnmangled[mangled] = unmangled + data.unmangledToMangled[unmangled] = mangled + return + + limit = 0 + m = re.match(r"^\w (?:/(\d+))? ", line) + if m: + limit = int(m[1]) + + tokens = line.split(" ") + if tokens[0] in ("D", "R"): + _, caller, callee = tokens + add_call(lookup(caller), lookup(callee), limit) + elif tokens[0] == "T": + data.tags[tokens[1]].add(line.split(" ", 2)[2]) + elif tokens[0] in ("F", "V"): + m = re.match(r"^[FV] (\d+) (\d+) CLASS (.*?) FIELD (.*)", line) + caller, callee, csu, field = m.groups() + add_call(lookup(caller), lookup(callee), limit) + + elif tokens[0] == "I": + m = re.match(r"^I (\d+) VARIABLE ([^\,]*)", line) + pass + + self.load_text_file("callgraph.txt", extract=process) + return data + + def load_hazards(self): + def grab_hazard(line): + m = re.match( + r"Function '(.*?)' has unrooted '(.*?)' of type '(.*?)' live across GC call '(.*?)' at (.*)", # NOQA: E501 + line, + ) + if m: + info = list(m.groups()) + info[0] = info[0].split("$")[-1] + info[3] = info[3].split("$")[-1] + return HazardSummary(*info) + return None + + return self.load_text_file("rootingHazards.txt", extract=grab_hazard) + + def process_body(self, body): + return Body(body) + + def process_bodies(self, bodies): + return [self.process_body(b) for b in bodies] diff --git a/js/src/devtools/rootAnalysis/t/virtual/source.cpp b/js/src/devtools/rootAnalysis/t/virtual/source.cpp new file mode 100644 index 0000000000..e3977b07e2 --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/virtual/source.cpp @@ -0,0 +1,169 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#define ANNOTATE(property) __attribute__((annotate(property))) + +extern void GC() ANNOTATE("GC Call"); + +void GC() { + // If the implementation is too trivial, the function body won't be emitted at + // all. + asm(""); +} + +struct Cell { + int f; +} ANNOTATE("GC Thing"); + +extern void foo(); + +typedef void (*func_t)(); + +class Base { + public: + int ANNOTATE("field annotation") dummy; + virtual void someGC() ANNOTATE("Base pure virtual method") = 0; + func_t functionField; + + // For now, this is just to verify that the plugin doesn't crash. The + // analysis code does not yet look at this annotation or output it anywhere + // (though it *is* being recorded.) + static float testAnnotations() ANNOTATE("static func"); + + // Similar, though sixgill currently completely ignores parameter annotations. + static double testParamAnnotations(Cell& ANNOTATE("param annotation") + ANNOTATE("second param annot") cell) + ANNOTATE("static func") ANNOTATE("second func"); +}; + +float Base::testAnnotations() { + asm(""); + return 1.1; +} + +double Base::testParamAnnotations(Cell& cell) { + asm(""); + return 1.2; +} + +class Super : public Base { + public: + virtual void noneGC() = 0; + virtual void allGC() = 0; +}; + +void bar() { GC(); } + +class Sub1 : public Super { + public: + void noneGC() override { foo(); } + void someGC() override ANNOTATE("Sub1 override") ANNOTATE("second attr") { + foo(); + } + void allGC() override { + foo(); + bar(); + } +} ANNOTATE("CSU1") ANNOTATE("CSU2"); + +class Sub2 : public Super { + public: + void noneGC() override { foo(); } + void someGC() override { + foo(); + bar(); + } + void allGC() override { + foo(); + bar(); + } +}; + +class Sibling : public Base { + public: + virtual void noneGC() { foo(); } + void someGC() override { + foo(); + bar(); + } + virtual void allGC() { + foo(); + bar(); + } +}; + +class AutoSuppressGC { + public: + AutoSuppressGC() {} + ~AutoSuppressGC() {} +} ANNOTATE("Suppress GC"); + +void use(Cell*) { asm(""); } + +void f() { + Sub1 s1; + Sub2 s2; + + Cell cell; + { + Cell* c1 = &cell; + s1.noneGC(); + use(c1); + } + { + Cell* c2 = &cell; + s2.someGC(); + use(c2); + } + { + Cell* c3 = &cell; + s1.allGC(); + use(c3); + } + { + Cell* c4 = &cell; + s2.noneGC(); + use(c4); + } + { + Cell* c5 = &cell; + s2.someGC(); + use(c5); + } + { + Cell* c6 = &cell; + s2.allGC(); + use(c6); + } + + Super* super = &s2; + { + Cell* c7 = &cell; + super->noneGC(); + use(c7); + } + { + Cell* c8 = &cell; + super->someGC(); + use(c8); + } + { + Cell* c9 = &cell; + super->allGC(); + use(c9); + } + + { + Cell* c10 = &cell; + s1.functionField(); + use(c10); + } + { + Cell* c11 = &cell; + super->functionField(); + use(c11); + } +} diff --git a/js/src/devtools/rootAnalysis/t/virtual/test.py b/js/src/devtools/rootAnalysis/t/virtual/test.py new file mode 100644 index 0000000000..a0e2a410ea --- /dev/null +++ b/js/src/devtools/rootAnalysis/t/virtual/test.py @@ -0,0 +1,48 @@ +# 'test' is provided by the calling script. +# flake8: noqa: F821 + +test.compile("source.cpp") +test.run_analysis_script("gcTypes") + +info = test.load_typeInfo() + +assert "Sub1" in info["OtherCSUTags"] +assert ["CSU1", "CSU2"] == sorted(info["OtherCSUTags"]["Sub1"]) +assert "Base" in info["OtherFieldTags"] +assert "someGC" in info["OtherFieldTags"]["Base"] +assert "Sub1" in info["OtherFieldTags"] +assert "someGC" in info["OtherFieldTags"]["Sub1"] +assert ["Sub1 override", "second attr"] == sorted( + info["OtherFieldTags"]["Sub1"]["someGC"] +) + +gcFunctions = test.load_gcFunctions() + +assert "void Sub1::noneGC()" not in gcFunctions +assert "void Sub1::someGC()" not in gcFunctions +assert "void Sub1::allGC()" in gcFunctions +assert "void Sub2::noneGC()" not in gcFunctions +assert "void Sub2::someGC()" in gcFunctions +assert "void Sub2::allGC()" in gcFunctions + +callgraph = test.load_callgraph() + +assert callgraph.calleeGraph["void f()"]["Super.noneGC"] +assert callgraph.calleeGraph["Super.noneGC"]["void Sub1::noneGC()"] +assert callgraph.calleeGraph["Super.noneGC"]["void Sub2::noneGC()"] +assert "void Sibling::noneGC()" not in callgraph.calleeGraph["Super.noneGC"] + +hazards = test.load_hazards() +hazmap = {haz.variable: haz for haz in hazards} + +assert "c1" not in hazmap +assert "c2" in hazmap +assert "c3" in hazmap +assert "c4" not in hazmap +assert "c5" in hazmap +assert "c6" in hazmap +assert "c7" not in hazmap +assert "c8" in hazmap +assert "c9" in hazmap +assert "c10" in hazmap +assert "c11" in hazmap diff --git a/js/src/devtools/rootAnalysis/utility.js b/js/src/devtools/rootAnalysis/utility.js new file mode 100644 index 0000000000..8df860facb --- /dev/null +++ b/js/src/devtools/rootAnalysis/utility.js @@ -0,0 +1,292 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ + +"use strict"; + +loadRelativeToScript('dumpCFG.js'); + +// Limit inset bits - each call edge may carry a set of 'limit' bits, saying eg +// that the edge takes place within a scope where GC is suppressed, for +// example. +var LIMIT_NONE = 0; +var LIMIT_CANNOT_GC = 1; +var LIMIT_ALL = 1; + +// The traversal algorithms we run will recurse into children if you change any +// limit bit to zero. Use all bits set to maximally limited, including +// additional bits that all just mean "unvisited", so that the first time we +// see a node with this limit, we're guaranteed to turn at least one bit off +// and thereby keep going. +var LIMIT_UNVISITED = 0xffff; + +// gcc appends this to mangled function names for "not in charge" +// constructors/destructors. +var internalMarker = " *INTERNAL* "; + +if (! Set.prototype.hasOwnProperty("update")) { + Object.defineProperty(Set.prototype, "update", { + value: function (collection) { + for (let elt of collection) + this.add(elt); + } + }); +} + +function assert(x, msg) +{ + if (x) + return; + debugger; + if (msg) + throw "assertion failed: " + msg + "\n" + (Error().stack); + else + throw "assertion failed: " + (Error().stack); +} + +function defined(x) { + return x !== undefined; +} + +function xprint(x, padding) +{ + if (!padding) + padding = ""; + if (x instanceof Array) { + print(padding + "["); + for (var elem of x) + xprint(elem, padding + " "); + print(padding + "]"); + } else if (x instanceof Object) { + print(padding + "{"); + for (var prop in x) { + print(padding + " " + prop + ":"); + xprint(x[prop], padding + " "); + } + print(padding + "}"); + } else { + print(padding + x); + } +} + +function parse_options(parameters, inArgs = scriptArgs) { + const options = {}; + + const optional = {}; + const positional = []; + for (const param of parameters) { + if (param.name.startsWith("-")) { + optional[param.name] = param; + param.dest = param.dest || param.name.substring(2).replace("-", "_"); + } else { + positional.push(param); + param.dest = param.dest || param.name.replace("-", "_"); + } + + param.type = param.type || 'bool'; + if ('default' in param) + options[param.dest] = param.default; + } + + options.rest = []; + const args = [...inArgs]; + while (args.length > 0) { + let param; + let pos = -1; + if (args[0] in optional) + param = optional[args[0]]; + else { + pos = args[0].indexOf("="); + if (pos != -1) { + param = optional[args[0].substring(0, pos)]; + pos++; + } + } + + if (!param) { + if (positional.length > 0) { + param = positional.shift(); + options[param.dest] = args.shift(); + } else { + options.rest.push(args.shift()); + } + continue; + } + + if (param.type != 'bool') { + if (pos != -1) { + options[param.dest] = args.shift().substring(pos); + } else { + args.shift(); + if (args.length == 0) + throw(new Error(`--${param.name} requires an argument`)); + options[param.dest] = args.shift(); + } + } else { + if (pos != -1) + throw(new Error(`--${param.name} does not take an argument`)); + options[param.dest] = true; + args.shift(); + } + } + + return options; +} + +function sameBlockId(id0, id1) +{ + if (id0.Kind != id1.Kind) + return false; + if (!sameVariable(id0.Variable, id1.Variable)) + return false; + if (id0.Kind == "Loop" && id0.Loop != id1.Loop) + return false; + return true; +} + +function sameVariable(var0, var1) +{ + assert("Name" in var0 || var0.Kind == "This" || var0.Kind == "Return"); + assert("Name" in var1 || var1.Kind == "This" || var1.Kind == "Return"); + if ("Name" in var0) + return "Name" in var1 && var0.Name[0] == var1.Name[0]; + return var0.Kind == var1.Kind; +} + +function blockIdentifier(body) +{ + if (body.BlockId.Kind == "Loop") + return body.BlockId.Loop; + assert(body.BlockId.Kind == "Function", "body.Kind should be Function, not " + body.BlockId.Kind); + return body.BlockId.Variable.Name[0]; +} + +function collectBodyEdges(body) +{ + body.predecessors = []; + body.successors = []; + if (!("PEdge" in body)) + return; + + for (var edge of body.PEdge) { + var [ source, target ] = edge.Index; + if (!(target in body.predecessors)) + body.predecessors[target] = []; + body.predecessors[target].push(edge); + if (!(source in body.successors)) + body.successors[source] = []; + body.successors[source].push(edge); + } +} + +function getPredecessors(body) +{ + try { + if (!('predecessors' in body)) + collectBodyEdges(body); + } catch (e) { + debugger; + printErr("body is " + body); + } + return body.predecessors; +} + +function getSuccessors(body) +{ + if (!('successors' in body)) + collectBodyEdges(body); + return body.successors; +} + +// Split apart a function from sixgill into its mangled and unmangled name. If +// no mangled name was given, use the unmangled name as its mangled name +function splitFunction(func) +{ + var split = func.indexOf("$"); + if (split != -1) + return [ func.substr(0, split), func.substr(split+1) ]; + split = func.indexOf("|"); + if (split != -1) + return [ func.substr(0, split), func.substr(split+1) ]; + return [ func, func ]; +} + +function mangled(fullname) +{ + var [ mangled, unmangled ] = splitFunction(fullname); + return mangled; +} + +function readable(fullname) +{ + var [ mangled, unmangled ] = splitFunction(fullname); + return unmangled; +} + +function xdbLibrary() +{ + var lib = ctypes.open(os.getenv('XDB')); + var api = { + open: lib.declare("xdb_open", ctypes.default_abi, ctypes.void_t, ctypes.char.ptr), + min_data_stream: lib.declare("xdb_min_data_stream", ctypes.default_abi, ctypes.int), + max_data_stream: lib.declare("xdb_max_data_stream", ctypes.default_abi, ctypes.int), + read_key: lib.declare("xdb_read_key", ctypes.default_abi, ctypes.char.ptr, ctypes.int), + read_entry: lib.declare("xdb_read_entry", ctypes.default_abi, ctypes.char.ptr, ctypes.char.ptr), + free_string: lib.declare("xdb_free", ctypes.default_abi, ctypes.void_t, ctypes.char.ptr) + }; + try { + api.lookup_key = lib.declare("xdb_lookup_key", ctypes.default_abi, ctypes.int, ctypes.char.ptr); + } catch (e) { + // lookup_key is for development use only and is not strictly necessary. + } + return api; +} + +function cLibrary() +{ + var libPossibilities = ['libc.so.6', 'libc.so', 'libc.dylib']; + var lib; + for (const name of libPossibilities) { + try { + lib = ctypes.open("libc.so.6"); + } catch(e) { + } + } + + return { + fopen: lib.declare("fopen", ctypes.default_abi, ctypes.void_t.ptr, ctypes.char.ptr, ctypes.char.ptr), + getline: lib.declare("getline", ctypes.default_abi, ctypes.ssize_t, ctypes.char.ptr.ptr, ctypes.size_t.ptr, ctypes.void_t.ptr), + fclose: lib.declare("fclose", ctypes.default_abi, ctypes.int, ctypes.void_t.ptr), + free: lib.declare("free", ctypes.default_abi, ctypes.void_t, ctypes.void_t.ptr), + }; +} + +function* readFileLines_gen(filename) +{ + var libc = cLibrary(); + var linebuf = ctypes.char.ptr(); + var bufsize = ctypes.size_t(0); + var fp = libc.fopen(filename, "r"); + if (fp.isNull()) + throw "Unable to open '" + filename + "'" + + while (libc.getline(linebuf.address(), bufsize.address(), fp) > 0) + yield linebuf.readString(); + libc.fclose(fp); + libc.free(ctypes.void_t.ptr(linebuf)); +} + +function addToKeyedList(collection, key, entry) +{ + if (!(key in collection)) + collection[key] = []; + collection[key].push(entry); + return collection[key]; +} + +function loadTypeInfo(filename) +{ + return JSON.parse(os.file.readFile(filename)); +} |