Source code
Revision control
Copy as Markdown
Other Tools
/* 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/. */
// Uses parallel arrays indexed by node ID to minimize allocations when
// processing large CC graphs.
export class ShutdownLeakPathFinder {
constructor() {
this.addressToIndex = new Map();
this.addresses = [];
this.names = [];
this.refcounts = [];
// Edges as parallel arrays.
this.edgeFroms = [];
this.edgeTos = [];
this.edgeNames = [];
// Sparse per-node properties.
this.rootKnownEdges = new Map();
this.garbageNodes = new Set();
// Reverse adjacency list, built after capture.
this.ownerOffsets = null;
}
async findAndPrintPaths(leakedWindows, logger) {
logger.info(
"ShutdownLeakPathFinder | Capturing CC graph to find leak paths " +
"for " +
leakedWindows.length +
" leaked window(s) - this may take a moment..."
);
this._captureGraph();
this._buildOwnerIndex();
logger.info(
"ShutdownLeakPathFinder | CC graph captured (" +
this.addresses.length +
" nodes). Searching for leak paths..."
);
for (let info of leakedWindows) {
let idx = this.addressToIndex.get(info.address);
if (idx === undefined) {
this._logLeak(logger, info, {
detail: "not found in CC graph at " + info.address,
});
continue;
}
let path = this._findPathToRoot(idx);
if (!path) {
let detail = "no path to root found";
if (this.garbageNodes.has(idx)) {
detail += " (garbage cycle)";
}
this._logLeak(logger, info, { idx, detail });
continue;
}
this._logLeak(logger, info, { path });
}
}
_captureGraph() {
let start = ChromeUtils.now();
let listener = Cu.createCCLogger();
listener = listener.allTraces();
listener.disableLog = true;
listener.wantAfterProcessing = true;
Cu.forceCC(listener);
while (listener.processNext(this)) {
// processNext returns true if there is more data.
}
ChromeUtils.addProfilerMarker("ShutdownLeaks:captureGraph", {
category: "Test",
startTime: start,
});
}
_buildOwnerIndex() {
let nodeCount = this.addresses.length;
let owners = new Array(nodeCount).fill(null);
for (let i = 0; i < this.edgeFroms.length; i++) {
let to = this.edgeTos[i];
if (!owners[to]) {
owners[to] = [i];
} else {
owners[to].push(i);
}
}
this.ownerOffsets = owners;
}
noteRefCountedObject(address, refCount, name) {
let idx = this._ensureIndex(address);
this.refcounts[idx] = refCount;
this.names[idx] = name;
}
noteGCedObject(address, marked, name) {
let idx = this._ensureIndex(address);
this.names[idx] = name;
}
noteEdge(fromAddress, toAddress, edgeName) {
this.edgeFroms.push(this._ensureIndex(fromAddress));
this.edgeTos.push(this._ensureIndex(toAddress));
this.edgeNames.push(edgeName);
}
noteWeakMapEntry(mapAddr, keyAddr, keyDelegateAddr, valueAddr) {
if (valueAddr == "0x0") {
return;
}
// A weak map entry keeps the value alive if both the map and the key are
// alive. As an approximation, we only record the edge from the key to the
// value, ignoring the path to the map (which is usually a global variable
// and less interesting). We also ignore key delegates.
let fromAddr = keyAddr != "0x0" ? keyAddr : mapAddr;
if (fromAddr == "0x0") {
return;
}
this.edgeFroms.push(this._ensureIndex(fromAddr));
this.edgeTos.push(this._ensureIndex(valueAddr));
this.edgeNames.push("WeakMap value via key " + keyAddr);
}
describeRoot(address, knownEdges) {
this.rootKnownEdges.set(this._ensureIndex(address), knownEdges);
}
describeGarbage(address) {
this.garbageNodes.add(this._ensureIndex(address));
}
_ensureIndex(address) {
let idx = this.addressToIndex.get(address);
if (idx === undefined) {
idx = this.addresses.length;
this.addressToIndex.set(address, idx);
this.addresses.push(address);
this.names.push("");
this.refcounts.push(0);
}
return idx;
}
// BFS backward through owners using a parent map for path reconstruction.
_findPathToRoot(targetIdx) {
let nodeCount = this.addresses.length;
let parentNode = new Int32Array(nodeCount).fill(-1);
let parentEdge = new Int32Array(nodeCount).fill(-1);
let visited = new Uint8Array(nodeCount);
visited[targetIdx] = 1;
let queue = [targetIdx];
let head = 0;
while (head < queue.length) {
let current = queue[head++];
if (this.rootKnownEdges.has(current)) {
let nodeIndices = [];
let edgeIndices = [];
let cur = current;
while (cur !== targetIdx) {
nodeIndices.push(cur);
edgeIndices.push(parentEdge[cur]);
cur = parentNode[cur];
}
nodeIndices.push(targetIdx);
return { nodeIndices, edgeIndices };
}
let owners = this.ownerOffsets[current];
if (!owners) {
continue;
}
for (let e of owners) {
let owner = this.edgeFroms[e];
if (!visited[owner]) {
visited[owner] = 1;
parentNode[owner] = current;
parentEdge[owner] = e;
queue.push(owner);
}
}
}
return null;
}
_extractURL(name) {
// CC node names for windows look like:
// "nsGlobalWindowInner # 124 inner chrome://browser/content/browser.xhtml"
// "nsGlobalWindowOuter # 123 outer "
let match = name.match(
/nsGlobalWindow(?:Inner|Outer) # \d+ (?:inner|outer) (\S+)/
);
return match ? match[1] : null;
}
_formatNode(idx) {
let name = this.names[idx];
// "JS Object (Function - getChromeURI)" -> "JS Function - getChromeURI"
name = name.replace(/^JS Object \((.+)\)$/, "JS $1");
let rootInfo = "";
if (this.rootKnownEdges.has(idx)) {
let unknownRefs = this.refcounts[idx] - this.rootKnownEdges.get(idx);
rootInfo = " [root, " + unknownRefs + " unknown ref(s)]";
}
return name + rootInfo;
}
// Log a leaked window as a structured test_status FAIL.
// If |path| is provided, format the retention path as the stack.
// Otherwise use |idx| (node index) and |detail| for context.
_logLeak(logger, windowInfo, { idx = null, detail = null, path = null }) {
let stack;
let url;
if (path) {
let { nodeIndices, edgeIndices } = path;
let lines = [];
for (let i = 0; i < nodeIndices.length; i++) {
let ni = nodeIndices[i];
let node = this._formatNode(ni) + " @ " + this.addresses[ni];
if (i === 0) {
lines.push(node);
} else {
lines.push(" " + this.edgeNames[edgeIndices[i - 1]] + " — " + node);
}
}
stack = lines.join("\n");
let targetIdx = nodeIndices[nodeIndices.length - 1];
url = this._extractURL(this.names[targetIdx]);
} else {
let nodeDesc =
idx != null ? this._formatNode(idx) : "serial=" + windowInfo.serial;
stack = nodeDesc + "\n" + detail;
url = idx != null ? this._extractURL(this.names[idx]) : null;
}
let data = {
test: windowInfo.test,
subtest: "Shutdown",
status: "FAIL",
expected: "PASS",
message:
"leaked window until shutdown [url = " + (url || "unknown") + "]",
stack,
};
if (windowInfo.time) {
data.time = windowInfo.time;
}
logger.logData("test_status", data);
}
}