SSL loadCallgraph.js Sprache: JAVA

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

quality69%

¤ Dauer der Verarbeitung: 0.18 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.