The Tor Browser: js/src/devtools/rootAnalysis/analyzeRoots.js@129ffea94266

Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.

     1 /* -*- Mode: Javascript; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

     3 "use strict";

     5 loadRelativeToScript('utility.js');

     6 loadRelativeToScript('annotations.js');

     7 loadRelativeToScript('CFG.js');

     9 var sourceRoot = (environment['SOURCE'] || '') + '/'

    11 var functionBodies;

    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]]";

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

    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;

    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;

    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;

    49 var match;

    50 var gcThings = {};

    51 var gcPointers = {};

    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;

    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 }

    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 }

    88 function edgeUsesVariable(edge, variable)

    89 {

    90     if (ignoreEdgeUse(edge, variable))

    91         return false;

    92     switch (edge.Kind) {

    94     case "Assign":

    95         if (expressionUsesVariable(edge.Exp[0], variable))

    96             return true;

    97         return expressionUsesVariable(edge.Exp[1], variable);

    99     case "Assume":

   100         return expressionUsesVariable(edge.Exp[0], variable);

   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;

   119     case "Loop":

   120         return false;

   122     default:

   123         assert(false);

   124     }

   125 }

   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 }

   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 }

   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     }

   165     if (edge.Kind != "Call")

   166         return false;

   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     }

   175     // Constructor calls kill their 'this' value.

   176     if ("PEdgeCallInstance" in edge) {

   177         do {

   178             var instance = edge.PEdgeCallInstance.Exp;

   180             // Kludge around incorrect dereference on some constructor calls.

   181             if (instance.Kind == "Drf")

   182                 instance = instance.Exp[0];

   184             if (instance.Kind != "Var" || !sameVariable(instance.Variable, variable))

   185                 break;

   187             var callee = edge.Exp[0];

   188             if (callee.Kind != "Var")

   189                 break;

   191             assert(callee.Variable.Kind == "Func");

   192             var calleeName = readable(callee.Variable.Name[0]);

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

   200             var lastColon = calleeName.lastIndexOf('::');

   201             if (lastColon < 0)

   202                 break;

   203             var constructorName = calleeName.substr(lastColon + 2);

   204             calleeName = calleeName.substr(0, lastColon);

   206             var lastTemplateOpen = calleeName.lastIndexOf('<');

   207             if (lastTemplateOpen >= 0)

   208                 calleeName = calleeName.substr(0, lastTemplateOpen);

   210             if (calleeName.endsWith(constructorName))

   211                 return true;

   212         } while (false);

   213     }

   215     return false;

   216 }

   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 }

   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).

   251     while (worklist.length) {

   252         var entry = worklist.pop();

   253         var body = entry.body, ppoint = entry.ppoint;

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

   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         }

   288         var predecessors = getPredecessors(body);

   289         if (!(ppoint in predecessors))

   290             continue;

   292         for (var edge of predecessors[ppoint]) {

   293             var source = edge.Index[0];

   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             }

   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             }

   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             }

   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     }

   336     return null;

   337 }

   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.

   344     for (var body of functionBodies) {

   345         body.seen = null;

   346         body.minimumUse = 0;

   347     }

   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 }

   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 }

   385 function computePrintedLines(functionName)

   386 {

   387     assert(!system("xdbfind src_body.xdb '" + functionName + "' > " + tmpfile));

   388     var lines = snarf(tmpfile).split('\n');

   390     for (var body of functionBodies)

   391         body.lines = [];

   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 }

   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 }

   430 function locationLine(text)

   431 {

   432     if (match = /:(\d+)$/.exec(text))

   433         return match[1];

   434     return 0;

   435 }

   437 function printEntryTrace(functionName, entry)

   438 {

   439     if (!functionBodies[0].lines)

   440         computePrintedLines(functionName);

   442     while (entry) {

   443         var ppoint = entry.ppoint;

   444         var lineText = findLocation(entry.body, ppoint);

   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         }

   469         print("    " + lineText + (edgeText ? ": " + edgeText : ""));

   470         entry = entry.why;

   471     }

   472 }

   474 function isRootedType(type)

   475 {

   476     return type.Kind == "CSU" && isRootedTypeName(type.Name);

   477 }

   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 }

   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 }

   546 if (batch == 1)

   547     print("Time: " + new Date);

   549 var xdb = xdbLibrary();

   550 xdb.open("src_body.xdb");

   552 var minStream = xdb.min_data_stream()|0;

   553 var maxStream = xdb.max_data_stream()|0;

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

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

   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 }

The Tor Browser / file revision

js/src/devtools/rootAnalysis/analyzeRoots.js@129ffea94266

js/src/devtools/rootAnalysis/analyzeRoots.js