computeGCTypes.js (21453B)
1 /* This Source Code Form is subject to the terms of the Mozilla Public 2 * License, v. 2.0. If a copy of the MPL was not distributed with this file, 3 * You can obtain one at http://mozilla.org/MPL/2.0/. */ 4 5 /* -*- indent-tabs-mode: nil; js-indent-level: 4 -*- */ 6 7 "use strict"; 8 9 loadRelativeToScript('utility.js'); 10 loadRelativeToScript('annotations.js'); 11 12 var options = parse_options([ 13 { name: '--verbose', type: 'bool' }, 14 { name: "gcTypes", default: "gcTypes.txt" }, 15 { name: "typeInfo", default: "typeInfo.txt" } 16 ]); 17 18 var typeInfo = { 19 'GCPointers': [], 20 'GCThings': [], 21 'GCInvalidated': [], 22 'GCRefs': [], 23 'NonGCTypes': {}, // unused 24 'NonGCPointers': {}, 25 'RootedGCThings': {}, 26 'RootedPointers': {}, 27 'RootedBases': {'JS::AutoGCRooter': true}, 28 'InheritFromTemplateArgs': {}, 29 'OtherCSUTags': {}, 30 'OtherFieldTags': {}, 31 32 // RAII types within which we should assume GC is suppressed, eg 33 // AutoSuppressGC. 34 'GCSuppressors': {}, 35 }; 36 37 var gDescriptors = new Map; // Map from descriptor string => Set of typeName 38 39 var structureParents = {}; // Map from field => list of <parent, fieldName> 40 var pointerParents = {}; // Map from field => list of <parent, fieldName> 41 var baseClasses = {}; // Map from struct name => list of base class name strings 42 var subClasses = {}; // Map from struct name => list of subclass name strings 43 44 var gcTypes = {}; // map from parent struct => Set of GC typed children 45 var gcPointers = {}; // map from parent struct => Set of GC typed children 46 var gcFields = new Map; 47 48 var rootedPointers = {}; 49 50 // Accumulate the base GC types before propagating info through the type graph, 51 // so that we can include edges from types processed later 52 // (eg MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS). 53 var pendingGCTypes = []; // array of [name, reason, ptrdness] 54 55 function processCSU(csu, body) 56 { 57 for (let { 'Name': [ annType, tag ] } of (body.Annotation || [])) { 58 if (annType != 'annotate') 59 continue; 60 61 if (tag == 'GC Pointer') 62 typeInfo.GCPointers.push(csu); 63 else if (tag == 'Invalidated by GC') 64 typeInfo.GCInvalidated.push(csu); 65 else if (tag == 'GC Pointer or Reference') 66 typeInfo.GCRefs.push(csu); 67 else if (tag == 'GC Thing') 68 typeInfo.GCThings.push(csu); 69 else if (tag == 'Suppressed GC Pointer') 70 typeInfo.NonGCPointers[csu] = true; 71 else if (tag == 'Rooted Pointer') 72 typeInfo.RootedPointers[csu] = true; 73 else if (tag == 'Rooted Base') 74 typeInfo.RootedBases[csu] = true; 75 else if (tag == 'Suppress GC') 76 typeInfo.GCSuppressors[csu] = true; 77 else if (tag == 'moz_inherit_type_annotations_from_template_args') 78 typeInfo.InheritFromTemplateArgs[csu] = true; 79 else 80 addToKeyedList(typeInfo.OtherCSUTags, csu, tag); 81 } 82 83 for (let { 'Base': base } of (body.CSUBaseClass || [])) 84 addBaseClass(csu, base); 85 86 for (const field of (body.DataField || [])) { 87 var type = field.Field.Type; 88 var fieldName = field.Field.Name[0]; 89 if (type.Kind == "Pointer") { 90 var target = type.Type; 91 if (target.Kind == "CSU") 92 addNestedPointer(csu, target.Name, fieldName); 93 } 94 if (type.Kind == "Array") { 95 var target = type.Type; 96 if (target.Kind == "CSU") 97 addNestedStructure(csu, target.Name, fieldName); 98 } 99 if (type.Kind == "CSU") 100 addNestedStructure(csu, type.Name, fieldName); 101 102 for (const { 'Name': [ annType, tag ] } of (field.Annotation || [])) { 103 if (!(csu in typeInfo.OtherFieldTags)) 104 typeInfo.OtherFieldTags[csu] = []; 105 addToKeyedList(typeInfo.OtherFieldTags[csu], fieldName, tag); 106 } 107 } 108 109 for (const funcfield of (body.FunctionField || [])) { 110 const fields = funcfield.Field; 111 // Pure virtual functions will not have field.Variable; others will. 112 for (const field of funcfield.Field) { 113 for (const {'Name': [annType, tag]} of (field.Annotation || [])) { 114 if (!(csu in typeInfo.OtherFieldTags)) 115 typeInfo.OtherFieldTags[csu] = {}; 116 addToKeyedList(typeInfo.OtherFieldTags[csu], field.Name[0], tag); 117 } 118 } 119 } 120 } 121 122 // csu.field is of type inner 123 function addNestedStructure(csu, inner, field) 124 { 125 if (!(inner in structureParents)) 126 structureParents[inner] = []; 127 128 // Skip fields that are really base classes, to avoid duplicating the base 129 // fields; addBaseClass already added a "base-N" name. 130 if (field.match(/^field:\d+$/) && (csu in baseClasses) && (baseClasses[csu].indexOf(inner) != -1)) 131 return; 132 133 structureParents[inner].push([ csu, field ]); 134 } 135 136 function addBaseClass(csu, base) { 137 if (!(csu in baseClasses)) 138 baseClasses[csu] = []; 139 baseClasses[csu].push(base); 140 if (!(base in subClasses)) 141 subClasses[base] = []; 142 subClasses[base].push(csu); 143 var k = baseClasses[csu].length; 144 addNestedStructure(csu, base, `<base-${k}>`); 145 } 146 147 function addNestedPointer(csu, inner, field) 148 { 149 if (!(inner in pointerParents)) 150 pointerParents[inner] = []; 151 pointerParents[inner].push([ csu, field ]); 152 } 153 154 var xdb = xdbLibrary(); 155 xdb.open("src_comp.xdb"); 156 157 var minStream = xdb.min_data_stream(); 158 var maxStream = xdb.max_data_stream(); 159 160 for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) { 161 var csu = xdb.read_key(csuIndex); 162 var data = xdb.read_entry(csu); 163 var json = JSON.parse(data.readString()); 164 assert(json.length == 1); 165 processCSU(csu.readString(), json[0]); 166 167 xdb.free_string(csu); 168 xdb.free_string(data); 169 } 170 171 for (const typename of extraRootedGCThings()) 172 typeInfo.RootedGCThings[typename] = true; 173 174 for (const typename of extraRootedPointers()) 175 typeInfo.RootedPointers[typename] = true; 176 177 // Everything that inherits from a "Rooted Base" is considered to be rooted. 178 // This is for things like CustomAutoRooter and its subclasses. 179 var basework = Object.keys(typeInfo.RootedBases); 180 while (basework.length) { 181 const base = basework.pop(); 182 typeInfo.RootedPointers[base] = true; 183 if (base in subClasses) 184 basework.push(...subClasses[base]); 185 } 186 187 // Now that we have the whole hierarchy set up, add all the types and propagate 188 // info. 189 for (const csu of typeInfo.GCThings) 190 addGCType(csu); 191 for (const csu of typeInfo.GCPointers) 192 addGCPointer(csu); 193 for (const csu of typeInfo.GCInvalidated) 194 addGCPointer(csu); 195 196 function parseTemplateType(typeName, validate=false) { 197 // We only want templatized types. `Foo<U, T>::Member` doesn't count. 198 // Foo<U, T>::Bar<X, Y> does count. Which turns out to be a simple rule: 199 // check whether the type ends in '>'. 200 if (!typeName.endsWith(">")) { 201 return [typeName, undefined]; 202 } 203 204 // "Tokenize" into angle brackets, commas, and everything else. We store 205 // match objects as tokens because we'll need the string offset after we 206 // finish grabbing the template parameters. 207 const tokens = []; 208 const tokenizer = /[<>,]|[^<>,]+/g; 209 let match; 210 while ((match = tokenizer.exec(typeName)) !== null) { 211 tokens.push(match); 212 } 213 214 // Walk backwards through the tokens, stopping when we find the matching 215 // open bracket. 216 const args = []; 217 let depth = 0; 218 let arg; 219 let first_result; 220 for (const match of tokens.reverse()) { 221 const token = match[0]; 222 if (depth == 1 && (token == ',' || token == '<')) { 223 // We've walked back to the beginning of a template parameter, 224 // where we will see either a comma or open bracket. 225 args.unshift(arg); 226 arg = ''; 227 } else if (depth == 0 && token == '>') { 228 arg = ''; // We just started. 229 } else { 230 arg = token + arg; 231 } 232 233 // Maintain the depth. 234 if (token == '<') { 235 // This could be bug 1728151. 236 assert(depth > 0, `Invalid type: too many '<' signs in '${typeName}'`); 237 depth--; 238 } else if (token == '>') { 239 depth++; 240 } 241 242 if (depth == 0) { 243 // We've walked out of the template parameter list. 244 // Record the results. 245 assert(args.length > 0); 246 const templateName = typeName.substr(0, match.index); 247 const result = [templateName, args.map(arg => arg.trim())]; 248 if (!validate) { 249 // Normal processing is to return the result the first time we 250 // get to the '<' that matches the terminal '>', without validating 251 // that the rest of the type name is balanced. 252 return result; 253 } else if (!first_result) { 254 // If we are validating, remember the result when we hit the 255 // first matching '<', but then keep processing the rest of 256 // the input string to count brackets. 257 first_result = result; 258 } 259 } 260 } 261 262 // This could be bug 1728151. 263 assert(depth == 0, `Invalid type: too many '>' signs in '${typeName}'`); 264 return first_result; 265 } 266 267 if (os.getenv("HAZARD_RUN_INTERNAL_TESTS")) { 268 function check_parse(typeName, result) { 269 assertEq(JSON.stringify(parseTemplateType(typeName)), JSON.stringify(result)); 270 } 271 272 check_parse("int", ["int", undefined]); 273 check_parse("Type<int>", ["Type", ["int"]]); 274 check_parse("Container<int, double>", ["Container", ["int", "double"]]); 275 check_parse("Container<Container<void, void>, double>", ["Container", ["Container<void, void>", "double"]]); 276 check_parse("Foo<Bar<a,b>,Bar<a,b>>::Container<Container<void, void>, double>", ["Foo<Bar<a,b>,Bar<a,b>>::Container", ["Container<void, void>", "double"]]); 277 check_parse("AlignedStorage2<TypedArray<foo>>", ["AlignedStorage2", ["TypedArray<foo>"]]); 278 check_parse("mozilla::AlignedStorage2<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> >", 279 [ 280 "mozilla::AlignedStorage2", 281 [ 282 "mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer>" 283 ] 284 ] 285 ); 286 check_parse( 287 "mozilla::ArrayIterator<const mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >&, nsTArray_Impl<mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >, nsTArrayInfallibleAllocator> >", 288 [ 289 "mozilla::ArrayIterator", 290 [ 291 "const mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >&", 292 "nsTArray_Impl<mozilla::dom::binding_detail::RecordEntry<nsTString<char16_t>, mozilla::dom::Nullable<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> > >, nsTArrayInfallibleAllocator>" 293 ] 294 ] 295 ); 296 297 function check_throws(f, exc) { 298 try { 299 f(); 300 } catch (e) { 301 assertEq(e.message.includes(exc), true, "incorrect exception: " + e.message); 302 return; 303 } 304 assertEq(undefined, exc); 305 } 306 // Note that these need to end in '>' or the whole thing will be ignored. 307 check_throws(() => parseTemplateType("foo>", true), "too many '>' signs"); 308 check_throws(() => parseTemplateType("foo<<>", true), "too many '<' signs"); 309 check_throws(() => parseTemplateType("foo<a::bar<a,b>", true), "too many '<' signs"); 310 check_throws(() => parseTemplateType("foo<a>*>::bar<a,b>", true), "too many '>' signs"); 311 } 312 313 // GC Thing and GC Pointer annotations can be inherited from template args if 314 // this annotation is used. Think of Maybe<T> for example: Maybe<JSObject*> has 315 // the same GC rules as JSObject*. 316 317 var inheritors = Object.keys(typeInfo.InheritFromTemplateArgs).sort((a, b) => a.length - b.length); 318 for (const csu of inheritors) { 319 const [templateName, templateArgs] = parseTemplateType(csu); 320 for (const param of (templateArgs || [])) { 321 const pos = param.search(/\**$/); 322 const ptrdness = param.length - pos; 323 const core_type = param.substr(0, pos); 324 if (ptrdness == 0) { 325 addToKeyedList(structureParents, core_type, [csu, "template-param-" + param]); 326 } else if (ptrdness == 1) { 327 addToKeyedList(pointerParents, core_type, [csu, "template-param-" + param]); 328 } 329 } 330 } 331 332 function Ptr(level) { 333 if (level < 0) 334 return Array(-level).fill("&").join(""); 335 else 336 return Array(level).fill("*").join(""); 337 } 338 339 // "typeName is a (pointer to a)^'typePtrLevel' GC type because it contains a field 340 // named 'child' of type 'childType' (or pointer to 'childType' if fieldPtrLevel == 1), 341 // which is itself a GCThing or GCPointer." 342 function markGCType(typeName, child, childType, typePtrLevel, fieldPtrLevel, indent = "") { 343 // Some types, like UniquePtr, do not mark/trace/relocate their contained 344 // pointers and so should not hold them live across a GC. UniquePtr in 345 // particular should be the only thing pointing to a structure containing a 346 // GCPointer, so nothing else can possibly trace it and it'll die when the 347 // UniquePtr goes out of scope. So we say that memory pointed to by a 348 // UniquePtr is just as unsafe as the stack for storing GC pointers. 349 if (isUnsafeStorage(typeName)) { 350 // If a UniquePtr<T> itself is on the stack, then there's a problem if 351 // T contains a Cell*. But the UniquePtr itself stores a T*, not a T, 352 // so set fieldPtrLevel=-1 to "undo" the pointer. When the type T is 353 // scanned for pointers and a Cell* is found, then when unwrapping the 354 // types, UniquePtr<T> will be seen as a T*=Cell** that should be 355 // treated as a Cell*. 356 // 357 // However, that creates the possibility of an infinite loop, if you 358 // have a type T that contains a UniquePtr<T> (which is allowed, because 359 // it's storing a T* not a T.) 360 const ptrLevel = typePtrLevel + fieldPtrLevel - 1; 361 if (options.verbose) { 362 printErr(`.${child} : (${childType} : "Cell${Ptr(typePtrLevel)}")${Ptr(fieldPtrLevel)} is-field-of ${typeName} : "Cell${Ptr(ptrLevel)}" [unsafe]`); 363 } 364 markGCTypeImpl(typeName, child, childType, ptrLevel, indent); 365 366 // Also treat UniquePtr<T> as if it were any other struct. 367 } 368 369 // Example: with: 370 // struct Pair { JSObject* foo; int bar; }; 371 // struct { Pair** info }*** 372 // make a call to: 373 // child='info' typePtrLevel=3 fieldPtrLevel=2 374 // for a final ptrLevel of 5, used to later call: 375 // child='foo' typePtrLevel=5 fieldPtrLevel=1 376 // 377 const ptrLevel = typePtrLevel + fieldPtrLevel; 378 if (options.verbose) { 379 printErr(`.${child} : (${childType} : "Cell${Ptr(typePtrLevel)}")${Ptr(fieldPtrLevel)} is-field-of ${typeName} : "Cell${Ptr(ptrLevel)}"`); 380 } 381 markGCTypeImpl(typeName, child, childType, ptrLevel, indent); 382 } 383 384 function markGCTypeImpl(typeName, child, childType, ptrLevel, indent) { 385 // ...except when > 2 levels of pointers away from an actual GC thing, stop 386 // searching the graph. (This would just be > 1, except that a UniquePtr 387 // field might still have a GC pointer.) 388 if (ptrLevel > 2) 389 return; 390 391 if (isRootedGCPointerTypeName(typeName) && !(typeName in typeInfo.RootedPointers)) 392 printErr("FIXME: use in-source annotation for " + typeName); 393 394 if (ptrLevel == 0 && (typeName in typeInfo.RootedGCThings)) 395 return; 396 if (ptrLevel == 1 && (isRootedGCPointerTypeName(typeName) || (typeName in typeInfo.RootedPointers))) 397 return; 398 399 if (ptrLevel == 0) { 400 if (typeName in typeInfo.NonGCTypes) 401 return; 402 if (!(typeName in gcTypes)) 403 gcTypes[typeName] = new Set(); 404 gcTypes[typeName].add(childType); 405 } else if (ptrLevel == 1) { 406 if (typeName in typeInfo.NonGCPointers) 407 return; 408 if (!(typeName in gcPointers)) 409 gcPointers[typeName] = new Set(); 410 gcPointers[typeName].add(childType); 411 } 412 413 if (ptrLevel < 2) { 414 if (!gcFields.has(typeName)) 415 gcFields.set(typeName, new Map()); 416 const fields = gcFields.get(typeName); 417 if (fields.has(child)) { 418 const [orig_childType, orig_ptrLevel] = fields.get(child); 419 if (ptrLevel >= orig_ptrLevel) { 420 // Do not recurse for things more levels of pointers away from Cell. 421 // This will prevent infinite loops when types are defined recursively 422 // (eg a struct containing a UniquePtr of itself). 423 return; 424 } 425 } 426 fields.set(child, [childType, ptrLevel]); 427 } 428 429 if (typeName in structureParents) { 430 for (var field of structureParents[typeName]) { 431 var [ holderType, fieldName ] = field; 432 markGCType(holderType, fieldName, typeName, ptrLevel, 0, indent + " "); 433 } 434 } 435 if (typeName in pointerParents) { 436 for (var field of pointerParents[typeName]) { 437 var [ holderType, fieldName ] = field; 438 markGCType(holderType, fieldName, typeName, ptrLevel, 1, indent + " "); 439 } 440 } 441 } 442 443 function addGCType(typeName) 444 { 445 pendingGCTypes.push([typeName, '<annotation>', '(annotation)', 0, 0]); 446 } 447 448 function addGCPointer(typeName) 449 { 450 pendingGCTypes.push([typeName, '<pointer-annotation>', '(annotation)', 1, 0]); 451 } 452 453 for (const pending of pendingGCTypes) { 454 markGCType(...pending); 455 } 456 457 // Call a function for a type and every type that contains the type in a field 458 // or as a base class (which internally is pretty much the same thing -- 459 // subclasses are structs beginning with the base class and adding on their 460 // local fields.) 461 function foreachContainingStruct(typeName, func, seen = new Set()) 462 { 463 function recurse(container, typeName) { 464 if (seen.has(typeName)) 465 return; 466 seen.add(typeName); 467 468 func(container, typeName); 469 470 if (typeName in subClasses) { 471 for (const sub of subClasses[typeName]) 472 recurse("subclass of " + typeName, sub); 473 } 474 if (typeName in structureParents) { 475 for (const [holder, field] of structureParents[typeName]) 476 recurse(field + " : " + typeName, holder); 477 } 478 } 479 480 recurse('<annotation>', typeName); 481 } 482 483 for (var type of listNonGCPointers()) 484 typeInfo.NonGCPointers[type] = true; 485 486 function explain(csu, indent, seen) { 487 if (!seen) 488 seen = new Set(); 489 seen.add(csu); 490 if (!gcFields.has(csu)) 491 return; 492 var fields = gcFields.get(csu); 493 494 if (fields.has('<annotation>')) { 495 print(indent + "which is annotated as a GCThing"); 496 return; 497 } 498 if (fields.has('<pointer-annotation>')) { 499 print(indent + "which is annotated as a GCPointer"); 500 return; 501 } 502 for (var [ field, [ child, ptrdness ] ] of fields) { 503 var msg = indent; 504 if (field[0] == '<') 505 msg += "inherits from "; 506 else { 507 if (field.startsWith("template-param-")) { 508 msg += "inherits annotations from template parameter '" + field.substr(15) + "' "; 509 } else { 510 msg += "contains field '" + field + "' "; 511 } 512 if (ptrdness == -1) 513 msg += "(with a pointer to unsafe storage) holding a "; 514 else if (ptrdness == 0) 515 msg += "of type "; 516 else 517 msg += "pointing to type "; 518 } 519 msg += child; 520 print(msg); 521 if (!seen.has(child)) 522 explain(child, indent + " ", seen); 523 } 524 } 525 526 var origOut = os.file.redirect(options.gcTypes); 527 528 for (var csu in gcTypes) { 529 print("GCThing: " + csu); 530 explain(csu, " "); 531 } 532 for (var csu in gcPointers) { 533 print("GCPointer: " + csu); 534 explain(csu, " "); 535 } 536 537 // Redirect output to the typeInfo file and close the gcTypes file. 538 os.file.close(os.file.redirect(options.typeInfo)); 539 540 // Compute the set of types that suppress GC within their RAII scopes (eg 541 // AutoSuppressGC, AutoSuppressGCForAnalysis). 542 var seen = new Set(); 543 for (let csu in typeInfo.GCSuppressors) 544 foreachContainingStruct(csu, 545 (holder, typeName) => { typeInfo.GCSuppressors[typeName] = holder }, 546 seen); 547 548 print(JSON.stringify(typeInfo, null, 4)); 549 550 os.file.close(os.file.redirect(origOut));