tor-browser

loadCallgraph.js (23601B)

---

/* 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('callgraph.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 gcEdges = {};

// Returns whether the function was added. (It will be refused if it was
// already there, or if attrs or annotations say it shouldn't be added.)
function addGCFunction(caller, reason, gcFunctions, functionAttrs, functions)
{
   if (functionAttrs[caller] && functionAttrs[caller][1] & ATTR_GC_SUPPRESSED)
       return false;

   if (ignoreGCFunction(functions.name[caller], functions.readableName))
       return false;

   if (!(caller in gcFunctions)) {
       gcFunctions[caller] = reason;
       return true;
   }

   return false;
}

// Every caller->callee callsite is associated with attrs saying what is
// allowed at that callsite (eg if it's in a GC suppression zone, it would have
// ATTR_GC_SUPPRESSED set.) A given caller might call the same callee multiple
// times, with different attributes. Associate the <caller,callee> edge with
// the intersection (AND) and disjunction (OR) of all of the callsites' attrs.
// The AND ('all') says what attributes are present for all callers; the OR
// ('any') says what attributes are present on any caller. Preserve the
// original order.
//
// During the same scan, build callersOf from calleesOf.
function generate_callgraph(rawCallees) {
   const callersOf = new Map();
   const calleesOf = new Map();

   for (const [caller, callee_attrs] of rawCallees) {
       const ordered_callees = [];

       // callee_attrs is a list of {callee,any,all} objects.
       const callee2any = new Map();
       const callee2all = new Map();
       for (const {callee, any, all} of callee_attrs) {
           const prev_any = callee2any.get(callee);
           if (prev_any === undefined) {
               assert(!callee2all.has(callee));
               callee2any.set(callee, any);
               callee2all.set(callee, all);
               ordered_callees.push(callee);
           } else {
               const prev_all = callee2all.get(callee);
               callee2any.set(callee, prev_any | any);
               callee2all.set(callee, prev_all & all);
           }
       }

       // Update the contents of callee_attrs to contain a single entry for
       // each callee, with its attrs set to the AND of the attrs observed at
       // all callsites within this caller function.
       callee_attrs.length = 0;
       for (const callee of ordered_callees) {
           const any = callee2any.get(callee);
           const all = callee2all.get(callee);
           if (!calleesOf.has(caller))
               calleesOf.set(caller, new Map());
           calleesOf.get(caller).set(callee, {any, all});
           if (!callersOf.has(callee))
               callersOf.set(callee, new Map());
           callersOf.get(callee).set(caller, {any, all});
       }
   }

   return {callersOf, calleesOf};
}

// Returns object mapping mangled => reason for GCing
function loadRawCallgraphFile(file, verbose)
{
   const functions = {
       // "Map" from identifier to mangled name, or sometimes to a Class.Field name.
       name: [""],

       // map from mangled name => list of readable names
       readableName: {},

       mangledToId: {}
   };

   const fieldCallAttrs = {};
   const fieldCallCSU = new Map(); // map from full field name id => csu name

   // set of mangled names (map from mangled name => [any,all])
   var functionAttrs = {};

   const gcCalls = [];
   const indirectCalls = [];

   // map from mangled => list of tuples of {'callee':mangled, 'any':intset, 'all':intset}
   const rawCallees = new Map();

   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(functions.name.length == id);
           functions.name.push(mangled);
           functions.mangledToId[mangled] = id|0;
           continue;
       }
       if (match = line.charAt(0) == "=" && /^= (\d+) (.*)/.exec(line)) {
           const [ _, id, readable ] = match;
           const mangled = functions.name[id];
           if (mangled in functions.readableName)
               functions.readableName[mangled].push(readable);
           else
               functions.readableName[mangled] = [ readable ];
           continue;
       }

       let attrs = 0;
       // Example line: D /17 6 7
       //
       // This means a direct call from 6 -> 7, but within a scope that
       // applies attrs 0x1 and 0x10 to the callee.
       //
       // Look for a bit specifier and remove it from the line if found.
       if (line.indexOf("/") != -1) {
           match = /^(..)\/(\d+) (.*)/.exec(line);
           line = match[1] + match[3];
           attrs = 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(functions.name[caller], name))
               attrs |= ATTR_GC_SUPPRESSED;
           indirectCalls.push([caller, "IndirectCall: " + name, attrs]);
       } else if (match = tag == 'F' && /^F (\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(functions.name[fullfield] == fullfield_str);
           if (attrs)
               fieldCallAttrs[fullfield] = attrs;
           addToMappedList(rawCallees, caller, {callee:fullfield, any:attrs, all:attrs});
           fieldCallCSU.set(fullfield, csu);

           if (fieldCallCannotGC(csu, fullfield_str))
               addToMappedList(rawCallees, fullfield, {callee:ID.nogcfunc, any:0, all:0});
           else
               addToMappedList(rawCallees, fullfield, {callee:ID.anyfunc, any:0, all:0});
       } else if (match = tag == 'V' && /^V (\d+) (\d+) CLASS (.*?) FIELD (.*)/.exec(line)) {
           // V tag is no longer used, but we are still emitting it becasue it
           // can be helpful to understand what's going on.
       } else if (match = tag == 'D' && /^D (\d+) (\d+)/.exec(line)) {
           const caller = match[1]|0;
           const callee = match[2]|0;
           addToMappedList(rawCallees, caller, {callee, any:attrs, all:attrs});
       } else if (match = tag == 'R' && /^R (\d+) (\d+)/.exec(line)) {
           assert(false, "R tag is no longer used");
       } else if (match = tag == 'T' && /^T (\d+) (.*)/.exec(line)) {
           const id = match[1]|0;
           let tag = match[2];
           if (tag == 'GC Call')
               gcCalls.push(id);
       } else {
           assert(false, "Invalid format in callgraph line: " + line);
       }
   }

   if (verbose) {
       printErr("Loaded[verbose=" + verbose + "] " + file);
   }

   return {
       fieldCallAttrs,
       fieldCallCSU,
       gcCalls,
       indirectCalls,
       rawCallees,
       functions
   };
}

// Take a set of rawcalls filenames (as in, the raw callgraph data output by
// computeCallgraph.js) and combine them into a global callgraph, renumbering
// the IDs as needed.
function mergeRawCallgraphs(filenames, verbose) {
   let d;
   for (const filename of filenames) {
       const raw = loadRawCallgraphFile(filename, verbose);
       if (!d) {
           d = raw;
           continue;
       }

       const {
           fieldCallAttrs,
           fieldCallCSU,
           gcCalls,
           indirectCalls,
           rawCallees,
           functions
       } = raw;

       // Compute the ID mapping. Incoming functions that already have an ID
       // will be mapped to that ID; new ones will allocate a fresh ID.
       const remap = new Array(functions.name.length);
       for (let i = 1; i < functions.name.length; i++) {
           const mangled = functions.name[i];
           const old_id = d.functions.mangledToId[mangled]
           if (old_id) {
               remap[i] = old_id;
           } else {
               const newid = d.functions.name.length;
               d.functions.mangledToId[mangled] = newid;
               d.functions.name.push(mangled);
               remap[i] = newid;
               assert(!(mangled in d.functions.readableName), mangled + " readable name is already found");
               const readables = functions.readableName[mangled];
               if (readables !== undefined)
                   d.functions.readableName[mangled] = readables;
           }
       }

       for (const [fullfield, attrs] of Object.entries(fieldCallAttrs))
           d.fieldCallAttrs[remap[fullfield]] = attrs;
       for (const [fullfield, csu] of fieldCallCSU.entries())
           d.fieldCallCSU.set(remap[fullfield], csu);
       for (const call of gcCalls)
           d.gcCalls.push(remap[call]);
       for (const [caller, name, attrs] of indirectCalls)
           d.indirectCalls.push([remap[caller], name, attrs]);
       for (const [caller, callees] of rawCallees) {
           for (const {callee, any, all} of callees) {
               addToMappedList(d.rawCallees, remap[caller]|0, {callee:remap[callee], any, all});
           }
       }
   }

   return d;
}

function loadCallgraph(files, verbose)
{
   const {
       fieldCallAttrs,
       fieldCallCSU,
       gcCalls,
       indirectCalls,
       rawCallees,
       functions
   } = mergeRawCallgraphs(files, verbose);

   assert(ID.jscode == functions.mangledToId["(js-code)"]);
   assert(ID.anyfunc == functions.mangledToId["(any-function)"]);
   assert(ID.nogcfunc == functions.mangledToId["(nogc-function)"]);
   assert(ID.gc == functions.mangledToId["(GC)"]);

   addToMappedList(rawCallees, functions.mangledToId["(any-function)"], {callee:ID.gc, any:0, all:0});

   // Compute functionAttrs: it should contain the set of functions that
   // are *always* called within some sort of limited context (eg GC
   // suppression).

   // set of mangled names (map from mangled name => [any,all])
   const functionAttrs = {};

   // Initialize to field calls with attrs set.
   for (var [name, attrs] of Object.entries(fieldCallAttrs))
       functionAttrs[name] = [attrs, attrs];

   // map from ID => reason
   const gcFunctions = { [ID.gc]: 'internal' };

   // 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(functions.readableName)) {
       addGCFunction(functions.mangledToId[func], "annotation", gcFunctions, functionAttrs, functions);
   }

   for (const func of gcCalls)
       addToMappedList(rawCallees, func, {callee:ID.gc, any:0, all:0});

   for (const [caller, indirect, attrs] of indirectCalls) {
       const id = functions.name.length;
       functions.name.push(indirect);
       functions.mangledToId[indirect] = id;
       addToMappedList(rawCallees, caller, {callee:id, any:attrs, all:attrs});
       addToMappedList(rawCallees, id, {callee:ID.anyfunc, any:0, all:0});
   }

   // Callers have a list of callees, with duplicates (if the same function is
   // called more than once.) Merge the repeated calls, only keeping attrs
   // that are in force for *every* callsite of that callee. Also, generate
   // the callersOf table at the same time.
   //
   // calleesOf : map from mangled => {mangled callee => {'any':intset, 'all':intset}}
   // callersOf : map from mangled => {mangled caller => {'any':intset, 'all':intset}}
   const {callersOf, calleesOf} = generate_callgraph(rawCallees);

   // Compute functionAttrs: it should contain the set of functions that
   // are *always* called within some sort of limited context (eg GC
   // suppression).

   // Initialize to field calls with attrs set.
   for (var [name, attrs] of Object.entries(fieldCallAttrs))
       functionAttrs[name] = [attrs, attrs];

   // Initialize functionAttrs to the set of all functions, where each one is
   // maximally attributed, and return a worklist containing all simple roots
   // (nodes with no callers).
   const simple_roots = gather_simple_roots(functionAttrs, calleesOf, callersOf);

   // Traverse the graph, spreading the attrs down from the roots.
   propagate_attrs(simple_roots, functionAttrs, 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.
   //
   // Simple example: in the JS shell build, moz_xstrdup calls itself, but
   // there are no calls to it from within js/src.
   const recursive_roots = gather_recursive_roots(functionAttrs, calleesOf, callersOf, functions);

   // And do a final traversal starting with the recursive roots.
   propagate_attrs(recursive_roots, functionAttrs, calleesOf);

   for (const [f, [any, all]] of Object.entries(functionAttrs)) {
       // Throw out all functions with no attrs set, to reduce the size of the
       // output. From now on, "not in functionAttrs" means [any=0, all=0].
       if (any == 0 && all == 0)
           delete functionAttrs[f];

       // Remove GC-suppressed functions from the set of functions known to GC.
       // Also remove functions only reachable through calls that have been
       // replaced.
       if (all & (ATTR_GC_SUPPRESSED | ATTR_REPLACED))
           delete gcFunctions[name];
   }

   // functionAttrs now contains all functions that are ever called in an
   // attributed context, based on the known callgraph (i.e., calls through
   // function pointers are not taken into consideration.)

   // 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(gcCalls.length > 0, "No GC functions found!");

   // Initialize the worklist to all known gcFunctions.
   const worklist = [ID.gc];

   // Include all field calls (but not virtual method calls).
   for (const [name, csuName] of fieldCallCSU) {
       const fullFieldName = functions.name[name];
       if (!fieldCallCannotGC(csuName, fullFieldName)) {
           gcFunctions[name] = 'arbitrary function pointer ' + 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 (!callersOf.has(name))
           continue;
       for (const [caller, {any, all}] of callersOf.get(name)) {
           if ((all & (ATTR_GC_SUPPRESSED | ATTR_REPLACED)) == 0) {
               if (addGCFunction(caller, name, gcFunctions, functionAttrs, functions))
                   worklist.push(caller);
           }
       }
   }

   // Convert functionAttrs to limitedFunctions (using mangled names instead
   // of ids.)

   // set of mangled names (map from mangled name => {any,all,recursive_root:bool}
   var limitedFunctions = {};

   for (const [id, [any, all]] of Object.entries(functionAttrs)) {
       if (all) {
           limitedFunctions[functions.name[id]] = { attributes: all };
       }
   }

   for (const [id, limits, label] of recursive_roots) {
       const name = functions.name[id];
       const s = limitedFunctions[name] || (limitedFunctions[name] = {});
       s.recursive_root = true;
   }

   // Remap ids to mangled names.
   const namedGCFunctions = {};
   for (const [caller, reason] of Object.entries(gcFunctions)) {
       namedGCFunctions[functions.name[caller]] = functions.name[reason] || reason;
   }

   return {
       gcFunctions: namedGCFunctions,
       functions,
       calleesOf,
       callersOf,
       limitedFunctions
   };
}

function saveCallgraph(functions, calleesOf) {
   // Write out all the ids and their readable names.
   let id = -1;
   for (const name of functions.name) {
       id += 1;
       if (id == 0) continue;
       print(`#${id} ${name}`);
       for (const readable of (functions.readableName[name] || [])) {
           if (readable != name)
               print(`= ${id} ${readable}`);
       }
   }

   // Omit field calls for now; let them appear as if they were functions.

   const attrstring = range => range.any || range.all ? `${range.all}:${range.any} ` : '';
   for (const [caller, callees] of calleesOf) {
       for (const [callee, attrs] of callees) {
           print(`D ${attrstring(attrs)}${caller} ${callee}`);
       }
   }

   // Omit tags for now. This really should preserve all tags. The "GC Call"
   // tag will already be represented in the graph by having an edge to the
   // "(GC)" node.
}

// Return a worklist of functions with no callers, and also initialize
// functionAttrs to the set of all functions, each mapped to
// [ATTRS_NONE, ATTRS_UNVISITED].
function gather_simple_roots(functionAttrs, calleesOf, callersOf) {
   const roots = [];
   for (const callee of callersOf.keys())
       functionAttrs[callee] = [ATTRS_NONE, ATTRS_UNVISITED];
   for (const caller of calleesOf.keys()) {
       functionAttrs[caller] = [ATTRS_NONE, ATTRS_UNVISITED];
       if (!callersOf.has(caller))
           roots.push([caller, ATTRS_NONE, 'root']);
   }

   return roots;
}

// Recursively traverse the callgraph from the roots. Recurse through every
// edge that weakens the attrs. (Attrs that entirely disappear, ie go to a zero
// intset, will be removed from functionAttrs.)
function propagate_attrs(roots, functionAttrs, calleesOf) {
   const worklist = Array.from(roots);
   let top = worklist.length;
   while (top > 0) {
       // Consider caller where (graph) -> caller -> (0 or more callees)
       // 'callercaller' is for debugging.
       const [caller, edge_attrs, callercaller] = worklist[--top];
       assert(caller in functionAttrs);
       const [prev_any, prev_all] = functionAttrs[caller];
       assert(prev_any !== undefined);
       assert(prev_all !== undefined);
       const [new_any, new_all] = [prev_any | edge_attrs, prev_all & edge_attrs];
       if (prev_any != new_any || prev_all != new_all) {
           // Update function attrs, then recurse to the children if anything
           // was updated.
           functionAttrs[caller] = [new_any, new_all];
           for (const [callee, {any, all}] of (calleesOf.get(caller) || new Map))
               worklist[top++] = [callee, all | edge_attrs, caller];
       }
   }
}

// Mutually-recursive roots and their descendants will not have been visited,
// and will still be set to [0, ATTRS_UNVISITED]. Scan through and gather them.
function gather_recursive_roots(functionAttrs, calleesOf, callersOf, functions) {
   const roots = [];

   // Pick any node. Mark everything reachable by adding to a 'seen' set. At
   // the end, if there are any incoming edges to that node from an unmarked
   // node, then it is not a root. Otherwise, mark the node as a root. (There
   // will be at least one back edge coming into the node from a marked node
   // in this case, since otherwise it would have already been considered to
   // be a root.)
   //
   // Repeat with remaining unmarked nodes until all nodes are marked.
   const seen = new Set();
   for (let [func, [any, all]] of Object.entries(functionAttrs)) {
       func = func|0;
       if (all != ATTRS_UNVISITED)
           continue;

       // We should only be looking at nodes with callers, since otherwise
       // they would have been handled in the previous pass!
       assert(callersOf.has(func));
       assert(callersOf.get(func).size > 0);

       if (seen.has(func))
           continue;

       const work = [func];
       while (work.length > 0) {
           const f = work.pop();
           if (!calleesOf.has(f)) continue;
           for (const callee of calleesOf.get(f).keys()) {
               if (!seen.has(callee) &&
                   callee != func &&
                   functionAttrs[callee][1] == ATTRS_UNVISITED)
               {
                   work.push(callee);
                   seen.add(callee);
               }
           }
       }

       assert(!seen.has(func));
       seen.add(func);
       if ([...callersOf.get(func).keys()].findIndex(f => !seen.has(f)) == -1) {
           // No unmarked incoming edges, including self-edges, so this is a
           // (recursive) root.
           roots.push([func, ATTRS_NONE, 'recursive-root']);
       }
   }

   return roots;

   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;
   }
}