The Tor Browser / file comparison

comparison: js/src/devtools/rootAnalysis/analyzeRoots.js

js/src/devtools/rootAnalysis/analyzeRoots.js

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:5181f2ea10bf
1 /* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
3 "use strict";
4
5 loadRelativeToScript('utility.js');
6 loadRelativeToScript('annotations.js');
7 loadRelativeToScript('CFG.js');
8
9 var sourceRoot = (environment['SOURCE'] || '') + '/'
10
11 var functionBodies;
12
13 if (typeof scriptArgs[0] != 'string' || typeof scriptArgs[1] != 'string')
14 throw "Usage: analyzeRoots.js <gcFunctions.lst> <gcEdges.txt> <suppressedFunctions.lst> <gcTypes.txt> [start end [tmpfile]]";
15
16 var gcFunctionsFile = scriptArgs[0];
17 var gcEdgesFile = scriptArgs[1];
18 var suppressedFunctionsFile = scriptArgs[2];
19 var gcTypesFile = scriptArgs[3];
20 var batch = (scriptArgs[4]|0) || 1;
21 var numBatches = (scriptArgs[5]|0) || 1;
22 var tmpfile = scriptArgs[6] || "tmp.txt";
23
24 var gcFunctions = {};
25 var text = snarf("gcFunctions.lst").split("\n");
26 assert(text.pop().length == 0);
27 for (var line of text)
28 gcFunctions[mangled(line)] = true;
29
30 var suppressedFunctions = {};
31 var text = snarf(suppressedFunctionsFile).split("\n");
32 assert(text.pop().length == 0);
33 for (var line of text) {
34 suppressedFunctions[line] = true;
35 }
36 text = null;
37
38 var gcEdges = {};
39 text = snarf(gcEdgesFile).split('\n');
40 assert(text.pop().length == 0);
41 for (var line of text) {
42 var [ block, edge, func ] = line.split(" || ");
43 if (!(block in gcEdges))
44 gcEdges[block] = {}
45 gcEdges[block][edge] = func;
46 }
47 text = null;
48
49 var match;
50 var gcThings = {};
51 var gcPointers = {};
52
53 text = snarf(gcTypesFile).split("\n");
54 for (var line of text) {
55 if (match = /^GCThing: (.*)/.exec(line))
56 gcThings[match[1]] = true;
57 if (match = /^GCPointer: (.*)/.exec(line))
58 gcPointers[match[1]] = true;
59 }
60 text = null;
61
62 function isUnrootedType(type)
63 {
64 if (type.Kind == "Pointer") {
65 var target = type.Type;
66 if (target.Kind == "CSU")
67 return target.Name in gcThings;
68 return false;
69 }
70 if (type.Kind == "CSU")
71 return type.Name in gcPointers;
72 return false;
73 }
74
75 function expressionUsesVariable(exp, variable)
76 {
77 if (exp.Kind == "Var" && sameVariable(exp.Variable, variable))
78 return true;
79 if (!("Exp" in exp))
80 return false;
81 for (var childExp of exp.Exp) {
82 if (expressionUsesVariable(childExp, variable))
83 return true;
84 }
85 return false;
86 }
87
88 function edgeUsesVariable(edge, variable)
89 {
90 if (ignoreEdgeUse(edge, variable))
91 return false;
92 switch (edge.Kind) {
93
94 case "Assign":
95 if (expressionUsesVariable(edge.Exp[0], variable))
96 return true;
97 return expressionUsesVariable(edge.Exp[1], variable);
98
99 case "Assume":
100 return expressionUsesVariable(edge.Exp[0], variable);
101
102 case "Call":
103 if (expressionUsesVariable(edge.Exp[0], variable))
104 return true;
105 if (1 in edge.Exp && expressionUsesVariable(edge.Exp[1], variable))
106 return true;
107 if ("PEdgeCallInstance" in edge) {
108 if (expressionUsesVariable(edge.PEdgeCallInstance.Exp, variable))
109 return true;
110 }
111 if ("PEdgeCallArguments" in edge) {
112 for (var exp of edge.PEdgeCallArguments.Exp) {
113 if (expressionUsesVariable(exp, variable))
114 return true;
115 }
116 }
117 return false;
118
119 case "Loop":
120 return false;
121
122 default:
123 assert(false);
124 }
125 }
126
127 function expressionIsVariableAddress(exp, variable)
128 {
129 while (exp.Kind == "Fld")
130 exp = exp.Exp[0];
131 return exp.Kind == "Var" && sameVariable(exp.Variable, variable);
132 }
133
134 function edgeTakesVariableAddress(edge, variable)
135 {
136 if (ignoreEdgeUse(edge, variable))
137 return false;
138 if (ignoreEdgeAddressTaken(edge))
139 return false;
140 switch (edge.Kind) {
141 case "Assign":
142 return expressionIsVariableAddress(edge.Exp[1], variable);
143 case "Call":
144 if ("PEdgeCallArguments" in edge) {
145 for (var exp of edge.PEdgeCallArguments.Exp) {
146 if (expressionIsVariableAddress(exp, variable))
147 return true;
148 }
149 }
150 return false;
151 default:
152 return false;
153 }
154 }
155
156 function edgeKillsVariable(edge, variable)
157 {
158 // Direct assignments kill their lhs.
159 if (edge.Kind == "Assign") {
160 var lhs = edge.Exp[0];
161 if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
162 return true;
163 }
164
165 if (edge.Kind != "Call")
166 return false;
167
168 // Assignments of call results kill their lhs.
169 if (1 in edge.Exp) {
170 var lhs = edge.Exp[1];
171 if (lhs.Kind == "Var" && sameVariable(lhs.Variable, variable))
172 return true;
173 }
174
175 // Constructor calls kill their 'this' value.
176 if ("PEdgeCallInstance" in edge) {
177 do {
178 var instance = edge.PEdgeCallInstance.Exp;
179
180 // Kludge around incorrect dereference on some constructor calls.
181 if (instance.Kind == "Drf")
182 instance = instance.Exp[0];
183
184 if (instance.Kind != "Var" || !sameVariable(instance.Variable, variable))
185 break;
186
187 var callee = edge.Exp[0];
188 if (callee.Kind != "Var")
189 break;
190
191 assert(callee.Variable.Kind == "Func");
192 var calleeName = readable(callee.Variable.Name[0]);
193
194 // Constructor calls include the text 'Name::Name(' or 'Name<...>::Name('.
195 var openParen = calleeName.indexOf('(');
196 if (openParen < 0)
197 break;
198 calleeName = calleeName.substring(0, openParen);
199
200 var lastColon = calleeName.lastIndexOf('::');
201 if (lastColon < 0)
202 break;
203 var constructorName = calleeName.substr(lastColon + 2);
204 calleeName = calleeName.substr(0, lastColon);
205
206 var lastTemplateOpen = calleeName.lastIndexOf('<');
207 if (lastTemplateOpen >= 0)
208 calleeName = calleeName.substr(0, lastTemplateOpen);
209
210 if (calleeName.endsWith(constructorName))
211 return true;
212 } while (false);
213 }
214
215 return false;
216 }
217
218 function edgeCanGC(edge)
219 {
220 if (edge.Kind != "Call")
221 return false;
222 var callee = edge.Exp[0];
223 if (callee.Kind == "Var") {
224 var variable = callee.Variable;
225 assert(variable.Kind == "Func");
226 var callee = mangled(variable.Name[0]);
227 if (callee in gcFunctions)
228 return "'" + variable.Name[0] + "'";
229 return null;
230 }
231 assert(callee.Kind == "Drf");
232 if (callee.Exp[0].Kind == "Fld") {
233 var field = callee.Exp[0].Field;
234 var csuName = field.FieldCSU.Type.Name;
235 var fullFieldName = csuName + "." + field.Name[0];
236 if (fieldCallCannotGC(csuName, fullFieldName))
237 return null;
238 return (fullFieldName in suppressedFunctions) ? null : fullFieldName;
239 }
240 assert(callee.Exp[0].Kind == "Var");
241 var varName = callee.Exp[0].Variable.Name[0];
242 return indirectCallCannotGC(functionName, varName) ? null : "*" + varName;
243 }
244
245 function variableUseFollowsGC(suppressed, variable, worklist)
246 {
247 // Scan through all edges following an unrooted variable use, using an
248 // explicit worklist. A worklist contains a following edge together with a
249 // description of where one of its predecessors GC'd (if any).
250
251 while (worklist.length) {
252 var entry = worklist.pop();
253 var body = entry.body, ppoint = entry.ppoint;
254
255 if (body.seen) {
256 if (ppoint in body.seen) {
257 var seenEntry = body.seen[ppoint];
258 if (!entry.gcInfo || seenEntry.gcInfo)
259 continue;
260 }
261 } else {
262 body.seen = [];
263 }
264 body.seen[ppoint] = {body:body, gcInfo:entry.gcInfo};
265
266 if (ppoint == body.Index[0]) {
267 if (body.BlockId.Kind == "Loop") {
268 // propagate to parents that enter the loop body.
269 if ("BlockPPoint" in body) {
270 for (var parent of body.BlockPPoint) {
271 var found = false;
272 for (var xbody of functionBodies) {
273 if (sameBlockId(xbody.BlockId, parent.BlockId)) {
274 assert(!found);
275 found = true;
276 worklist.push({body:xbody, ppoint:parent.Index,
277 gcInfo:entry.gcInfo, why:entry});
278 }
279 }
280 assert(found);
281 }
282 }
283 } else if (variable.Kind == "Arg" && entry.gcInfo) {
284 return {gcInfo:entry.gcInfo, why:entry};
285 }
286 }
287
288 var predecessors = getPredecessors(body);
289 if (!(ppoint in predecessors))
290 continue;
291
292 for (var edge of predecessors[ppoint]) {
293 var source = edge.Index[0];
294
295 if (edgeKillsVariable(edge, variable)) {
296 if (entry.gcInfo)
297 return {gcInfo:entry.gcInfo, why:entry};
298 if (!body.minimumUse || source < body.minimumUse)
299 body.minimumUse = source;
300 continue;
301 }
302
303 var gcInfo = entry.gcInfo;
304 if (!gcInfo && !(source in body.suppressed) && !suppressed) {
305 var gcName = edgeCanGC(edge, body);
306 if (gcName)
307 gcInfo = {name:gcName, body:body, ppoint:source};
308 }
309
310 if (edgeUsesVariable(edge, variable)) {
311 if (gcInfo)
312 return {gcInfo:gcInfo, why:entry};
313 if (!body.minimumUse || source < body.minimumUse)
314 body.minimumUse = source;
315 }
316
317 if (edge.Kind == "Loop") {
318 // propagate to exit points of the loop body, in addition to the
319 // predecessor of the loop edge itself.
320 var found = false;
321 for (var xbody of functionBodies) {
322 if (sameBlockId(xbody.BlockId, edge.BlockId)) {
323 assert(!found);
324 found = true;
325 worklist.push({body:xbody, ppoint:xbody.Index[1],
326 gcInfo:gcInfo, why:entry});
327 }
328 }
329 assert(found);
330 break;
331 }
332 worklist.push({body:body, ppoint:source, gcInfo:gcInfo, why:entry});
333 }
334 }
335
336 return null;
337 }
338
339 function variableLiveAcrossGC(suppressed, variable)
340 {
341 // A variable is live across a GC if (1) it is used by an edge, and (2) it
342 // is used after a GC in a successor edge.
343
344 for (var body of functionBodies) {
345 body.seen = null;
346 body.minimumUse = 0;
347 }
348
349 for (var body of functionBodies) {
350 if (!("PEdge" in body))
351 continue;
352 for (var edge of body.PEdge) {
353 if (edgeUsesVariable(edge, variable) && !edgeKillsVariable(edge, variable)) {
354 var worklist = [{body:body, ppoint:edge.Index[0], gcInfo:null, why:null}];
355 var call = variableUseFollowsGC(suppressed, variable, worklist);
356 if (call)
357 return call;
358 }
359 }
360 }
361 return null;
362 }
363
364 // An unrooted variable has its address stored in another variable via
365 // assignment, or passed into a function that can GC. If the address is
366 // assigned into some other variable, we can't track it to see if it is held
367 // live across a GC. If it is passed into a function that can GC, then it's
368 // sort of like a Handle to an unrooted location, and the callee could GC
369 // before overwriting it or rooting it.
370 function unsafeVariableAddressTaken(suppressed, variable)
371 {
372 for (var body of functionBodies) {
373 if (!("PEdge" in body))
374 continue;
375 for (var edge of body.PEdge) {
376 if (edgeTakesVariableAddress(edge, variable)) {
377 if (edge.Kind == "Assign" || (!suppressed && edgeCanGC(edge)))
378 return {body:body, ppoint:edge.Index[0]};
379 }
380 }
381 }
382 return null;
383 }
384
385 function computePrintedLines(functionName)
386 {
387 assert(!system("xdbfind src_body.xdb '" + functionName + "' > " + tmpfile));
388 var lines = snarf(tmpfile).split('\n');
389
390 for (var body of functionBodies)
391 body.lines = [];
392
393 // Distribute lines of output to the block they originate from.
394 var currentBody = null;
395 for (var i = 0; i < lines.length; i++) {
396 var line = lines[i];
397 if (/^block:/.test(line)) {
398 if (match = /:(loop#[\d#]+)/.exec(line)) {
399 var loop = match[1];
400 var found = false;
401 for (var body of functionBodies) {
402 if (body.BlockId.Kind == "Loop" && body.BlockId.Loop == loop) {
403 assert(!found);
404 found = true;
405 currentBody = body;
406 }
407 }
408 assert(found);
409 } else {
410 for (var body of functionBodies) {
411 if (body.BlockId.Kind == "Function")
412 currentBody = body;
413 }
414 }
415 }
416 if (currentBody)
417 currentBody.lines.push(line);
418 }
419 }
420
421 function findLocation(body, ppoint)
422 {
423 var location = body.PPoint[ppoint - 1].Location;
424 var text = location.CacheString + ":" + location.Line;
425 if (text.indexOf(sourceRoot) == 0)
426 return text.substring(sourceRoot.length);
427 return text;
428 }
429
430 function locationLine(text)
431 {
432 if (match = /:(\d+)$/.exec(text))
433 return match[1];
434 return 0;
435 }
436
437 function printEntryTrace(functionName, entry)
438 {
439 if (!functionBodies[0].lines)
440 computePrintedLines(functionName);
441
442 while (entry) {
443 var ppoint = entry.ppoint;
444 var lineText = findLocation(entry.body, ppoint);
445
446 var edgeText = null;
447 if (entry.why && entry.why.body == entry.body) {
448 // If the next point in the trace is in the same block, look for an edge between them.
449 var next = entry.why.ppoint;
450 for (var line of entry.body.lines) {
451 if (match = /\((\d+),(\d+),/.exec(line)) {
452 if (match[1] == ppoint && match[2] == next)
453 edgeText = line; // May be multiple
454 }
455 }
456 assert(edgeText);
457 } else {
458 // Look for any outgoing edge from the chosen point.
459 for (var line of entry.body.lines) {
460 if (match = /\((\d+),/.exec(line)) {
461 if (match[1] == ppoint) {
462 edgeText = line;
463 break;
464 }
465 }
466 }
467 }
468
469 print(" " + lineText + (edgeText ? ": " + edgeText : ""));
470 entry = entry.why;
471 }
472 }
473
474 function isRootedType(type)
475 {
476 return type.Kind == "CSU" && isRootedTypeName(type.Name);
477 }
478
479 function typeDesc(type)
480 {
481 if (type.Kind == "CSU") {
482 return type.Name;
483 } else if ('Type' in type) {
484 var inner = typeDesc(type.Type);
485 if (type.Kind == 'Pointer')
486 return inner + '*';
487 else if (type.Kind == 'Array')
488 return inner + '[]';
489 else
490 return inner + '?';
491 } else {
492 return '???';
493 }
494 }
495
496 function processBodies(functionName)
497 {
498 if (!("DefineVariable" in functionBodies[0]))
499 return;
500 var suppressed = (mangled(functionName) in suppressedFunctions);
501 for (var variable of functionBodies[0].DefineVariable) {
502 if (variable.Variable.Kind == "Return")
503 continue;
504 var name;
505 if (variable.Variable.Kind == "This")
506 name = "this";
507 else
508 name = variable.Variable.Name[0];
509 if (isRootedType(variable.Type)) {
510 if (!variableLiveAcrossGC(suppressed, variable.Variable)) {
511 // The earliest use of the variable should be its constructor.
512 var lineText;
513 for (var body of functionBodies) {
514 if (body.minimumUse) {
515 var text = findLocation(body, body.minimumUse);
516 if (!lineText || locationLine(lineText) > locationLine(text))
517 lineText = text;
518 }
519 }
520 print("\nFunction '" + functionName + "'" +
521 " has unnecessary root '" + name + "' at " + lineText);
522 }
523 } else if (isUnrootedType(variable.Type)) {
524 var result = variableLiveAcrossGC(suppressed, variable.Variable);
525 if (result) {
526 var lineText = findLocation(result.gcInfo.body, result.gcInfo.ppoint);
527 print("\nFunction '" + functionName + "'" +
528 " has unrooted '" + name + "'" +
529 " of type '" + typeDesc(variable.Type) + "'" +
530 " live across GC call " + result.gcInfo.name +
531 " at " + lineText);
532 printEntryTrace(functionName, result.why);
533 }
534 result = unsafeVariableAddressTaken(suppressed, variable.Variable);
535 if (result) {
536 var lineText = findLocation(result.body, result.ppoint);
537 print("\nFunction '" + functionName + "'" +
538 " takes unsafe address of unrooted '" + name + "'" +
539 " at " + lineText);
540 printEntryTrace(functionName, {body:result.body, ppoint:result.ppoint});
541 }
542 }
543 }
544 }
545
546 if (batch == 1)
547 print("Time: " + new Date);
548
549 var xdb = xdbLibrary();
550 xdb.open("src_body.xdb");
551
552 var minStream = xdb.min_data_stream()|0;
553 var maxStream = xdb.max_data_stream()|0;
554
555 var N = (maxStream - minStream) + 1;
556 var each = Math.floor(N/numBatches);
557 var start = minStream + each * (batch - 1);
558 var end = Math.min(minStream + each * batch - 1, maxStream);
559
560 for (var nameIndex = start; nameIndex <= end; nameIndex++) {
561 var name = xdb.read_key(nameIndex);
562 var functionName = name.readString();
563 var data = xdb.read_entry(name);
564 xdb.free_string(name);
565 var json = data.readString();
566 xdb.free_string(data);
567 functionBodies = JSON.parse(json);
568
569 for (var body of functionBodies)
570 body.suppressed = [];
571 for (var body of functionBodies) {
572 for (var [pbody, id] of allRAIIGuardedCallPoints(body, isSuppressConstructor))
573 pbody.suppressed[id] = true;
574 }
575 processBodies(functionName);
576 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial