diff options
Diffstat (limited to 'js/src/devtools/rootAnalysis/computeGCTypes.js')
| -rw-r--r-- | js/src/devtools/rootAnalysis/computeGCTypes.js | 516 |
1 files changed, 516 insertions, 0 deletions
diff --git a/js/src/devtools/rootAnalysis/computeGCTypes.js b/js/src/devtools/rootAnalysis/computeGCTypes.js new file mode 100644 index 0000000000..eb327da5d2 --- /dev/null +++ b/js/src/devtools/rootAnalysis/computeGCTypes.js @@ -0,0 +1,516 @@ +/* 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('annotations.js'); + +var options = parse_options([ + { name: "gcTypes", default: "gcTypes.txt" }, + { name: "typeInfo", default: "typeInfo.txt" } +]); + +var typeInfo = { + 'GCPointers': [], + 'GCThings': [], + 'GCInvalidated': [], + 'GCRefs': [], + 'NonGCTypes': {}, // unused + 'NonGCPointers': {}, + 'RootedGCThings': {}, + 'RootedPointers': {}, + 'RootedBases': {'JS::AutoGCRooter': true}, + 'InheritFromTemplateArgs': {}, + 'OtherCSUTags': {}, + 'OtherFieldTags': {}, + + // RAII types within which we should assume GC is suppressed, eg + // AutoSuppressGC. + 'GCSuppressors': {}, +}; + +var gDescriptors = new Map; // Map from descriptor string => Set of typeName + +var structureParents = {}; // Map from field => list of <parent, fieldName> +var pointerParents = {}; // Map from field => list of <parent, fieldName> +var baseClasses = {}; // Map from struct name => list of base class name strings +var subClasses = {}; // Map from struct name => list of subclass name strings + +var gcTypes = {}; // map from parent struct => Set of GC typed children +var gcPointers = {}; // map from parent struct => Set of GC typed children +var gcFields = new Map; + +var rootedPointers = {}; + +// Accumulate the base GC types before propagating info through the type graph, +// so that we can include edges from types processed later +// (eg MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS). +var pendingGCTypes = []; // array of [name, reason, ptrdness] + +function processCSU(csu, body) +{ + for (let { 'Name': [ annType, tag ] } of (body.Annotation || [])) { + if (annType != 'annotate') + continue; + + if (tag == 'GC Pointer') + typeInfo.GCPointers.push(csu); + else if (tag == 'Invalidated by GC') + typeInfo.GCInvalidated.push(csu); + else if (tag == 'GC Pointer or Reference') + typeInfo.GCRefs.push(csu); + else if (tag == 'GC Thing') + typeInfo.GCThings.push(csu); + else if (tag == 'Suppressed GC Pointer') + typeInfo.NonGCPointers[csu] = true; + else if (tag == 'Rooted Pointer') + typeInfo.RootedPointers[csu] = true; + else if (tag == 'Rooted Base') + typeInfo.RootedBases[csu] = true; + else if (tag == 'Suppress GC') + typeInfo.GCSuppressors[csu] = true; + else if (tag == 'moz_inherit_type_annotations_from_template_args') + typeInfo.InheritFromTemplateArgs[csu] = true; + else + addToKeyedList(typeInfo.OtherCSUTags, csu, tag); + } + + for (let { 'Base': base } of (body.CSUBaseClass || [])) + addBaseClass(csu, base); + + for (const field of (body.DataField || [])) { + var type = field.Field.Type; + var fieldName = field.Field.Name[0]; + if (type.Kind == "Pointer") { + var target = type.Type; + if (target.Kind == "CSU") + addNestedPointer(csu, target.Name, fieldName); + } + if (type.Kind == "Array") { + var target = type.Type; + if (target.Kind == "CSU") + addNestedStructure(csu, target.Name, fieldName); + } + if (type.Kind == "CSU") + addNestedStructure(csu, type.Name, fieldName); + + for (const { 'Name': [ annType, tag ] } of (field.Annotation || [])) { + if (!(csu in typeInfo.OtherFieldTags)) + typeInfo.OtherFieldTags[csu] = []; + addToKeyedList(typeInfo.OtherFieldTags[csu], fieldName, tag); + } + } + + for (const funcfield of (body.FunctionField || [])) { + const fields = funcfield.Field; + // Pure virtual functions will not have field.Variable; others will. + for (const field of funcfield.Field) { + for (const {'Name': [annType, tag]} of (field.Annotation || [])) { + if (!(csu in typeInfo.OtherFieldTags)) + typeInfo.OtherFieldTags[csu] = {}; + addToKeyedList(typeInfo.OtherFieldTags[csu], field.Name[0], tag); + } + } + } +} + +// csu.field is of type inner +function addNestedStructure(csu, inner, field) +{ + if (!(inner in structureParents)) + structureParents[inner] = []; + + // Skip fields that are really base classes, to avoid duplicating the base + // fields; addBaseClass already added a "base-N" name. + if (field.match(/^field:\d+$/) && (csu in baseClasses) && (baseClasses[csu].indexOf(inner) != -1)) + return; + + structureParents[inner].push([ csu, field ]); +} + +function addBaseClass(csu, base) { + if (!(csu in baseClasses)) + baseClasses[csu] = []; + baseClasses[csu].push(base); + if (!(base in subClasses)) + subClasses[base] = []; + subClasses[base].push(csu); + var k = baseClasses[csu].length; + addNestedStructure(csu, base, `<base-${k}>`); +} + +function addNestedPointer(csu, inner, field) +{ + if (!(inner in pointerParents)) + pointerParents[inner] = []; + pointerParents[inner].push([ csu, field ]); +} + +var xdb = xdbLibrary(); +xdb.open("src_comp.xdb"); + +var minStream = xdb.min_data_stream(); +var maxStream = xdb.max_data_stream(); + +for (var csuIndex = minStream; csuIndex <= maxStream; csuIndex++) { + var csu = xdb.read_key(csuIndex); + var data = xdb.read_entry(csu); + var json = JSON.parse(data.readString()); + assert(json.length == 1); + processCSU(csu.readString(), json[0]); + + xdb.free_string(csu); + xdb.free_string(data); +} + +for (const typename of extraRootedGCThings()) + typeInfo.RootedGCThings[typename] = true; + +for (const typename of extraRootedPointers()) + typeInfo.RootedPointers[typename] = true; + +// Everything that inherits from a "Rooted Base" is considered to be rooted. +// This is for things like CustomAutoRooter and its subclasses. +var basework = Object.keys(typeInfo.RootedBases); +while (basework.length) { + const base = basework.pop(); + typeInfo.RootedPointers[base] = true; + if (base in subClasses) + basework.push(...subClasses[base]); +} + +// Now that we have the whole hierarchy set up, add all the types and propagate +// info. +for (const csu of typeInfo.GCThings) + addGCType(csu); +for (const csu of typeInfo.GCPointers) + addGCPointer(csu); +for (const csu of typeInfo.GCInvalidated) + addGCPointer(csu); + +function parseTemplateType(typeName, validate=false) { + // We only want templatized types. `Foo<U, T>::Member` doesn't count. + // Foo<U, T>::Bar<X, Y> does count. Which turns out to be a simple rule: + // check whether the type ends in '>'. + if (!typeName.endsWith(">")) { + return [typeName, undefined]; + } + + // "Tokenize" into angle brackets, commas, and everything else. We store + // match objects as tokens because we'll need the string offset after we + // finish grabbing the template parameters. + const tokens = []; + const tokenizer = /[<>,]|[^<>,]+/g; + let match; + while ((match = tokenizer.exec(typeName)) !== null) { + tokens.push(match); + } + + // Walk backwards through the tokens, stopping when we find the matching + // open bracket. + const args = []; + let depth = 0; + let arg; + let first_result; + for (const match of tokens.reverse()) { + const token = match[0]; + if (depth == 1 && (token == ',' || token == '<')) { + // We've walked back to the beginning of a template parameter, + // where we will see either a comma or open bracket. + args.unshift(arg); + arg = ''; + } else if (depth == 0 && token == '>') { + arg = ''; // We just started. + } else { + arg = token + arg; + } + + // Maintain the depth. + if (token == '<') { + // This could be bug 1728151. + assert(depth > 0, `Invalid type: too many '<' signs in '${typeName}'`); + depth--; + } else if (token == '>') { + depth++; + } + + if (depth == 0) { + // We've walked out of the template parameter list. + // Record the results. + assert(args.length > 0); + const templateName = typeName.substr(0, match.index); + const result = [templateName, args.map(arg => arg.trim())]; + if (!validate) { + // Normal processing is to return the result the first time we + // get to the '<' that matches the terminal '>', without validating + // that the rest of the type name is balanced. + return result; + } else if (!first_result) { + // If we are validating, remember the result when we hit the + // first matching '<', but then keep processing the rest of + // the input string to count brackets. + first_result = result; + } + } + } + + // This could be bug 1728151. + assert(depth == 0, `Invalid type: too many '>' signs in '${typeName}'`); + return first_result; +} + +if (os.getenv("HAZARD_RUN_INTERNAL_TESTS")) { + function check_parse(typeName, result) { + assertEq(JSON.stringify(parseTemplateType(typeName)), JSON.stringify(result)); + } + + check_parse("int", ["int", undefined]); + check_parse("Type<int>", ["Type", ["int"]]); + check_parse("Container<int, double>", ["Container", ["int", "double"]]); + check_parse("Container<Container<void, void>, double>", ["Container", ["Container<void, void>", "double"]]); + 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"]]); + check_parse("AlignedStorage2<TypedArray<foo>>", ["AlignedStorage2", ["TypedArray<foo>"]]); + check_parse("mozilla::AlignedStorage2<mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer> >", + [ + "mozilla::AlignedStorage2", + [ + "mozilla::dom::TypedArray<unsigned char, JS::UnwrapArrayBufferMaybeShared, JS::GetArrayBufferMaybeSharedData, JS::GetArrayBufferMaybeSharedLengthAndData, JS::NewArrayBuffer>" + ] + ] + ); + check_parse( + "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> >", + [ + "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>" + ] + ] + ); + + function check_throws(f, exc) { + try { + f(); + } catch (e) { + assertEq(e.message.includes(exc), true, "incorrect exception: " + e.message); + return; + } + assertEq(undefined, exc); + } + // Note that these need to end in '>' or the whole thing will be ignored. + check_throws(() => parseTemplateType("foo>", true), "too many '>' signs"); + check_throws(() => parseTemplateType("foo<<>", true), "too many '<' signs"); + check_throws(() => parseTemplateType("foo<a::bar<a,b>", true), "too many '<' signs"); + check_throws(() => parseTemplateType("foo<a>*>::bar<a,b>", true), "too many '>' signs"); +} + +// GC Thing and GC Pointer annotations can be inherited from template args if +// this annotation is used. Think of Maybe<T> for example: Maybe<JSObject*> has +// the same GC rules as JSObject*. + +var inheritors = Object.keys(typeInfo.InheritFromTemplateArgs).sort((a, b) => a.length - b.length); +for (const csu of inheritors) { + const [templateName, templateArgs] = parseTemplateType(csu); + for (const param of templateArgs) { + const pos = param.search(/\**$/); + const ptrdness = param.length - pos; + const core_type = param.substr(0, pos); + if (ptrdness == 0) { + addToKeyedList(structureParents, core_type, [csu, "template-param-" + param]); + } else if (ptrdness == 1) { + addToKeyedList(pointerParents, core_type, [csu, "template-param-" + param]); + } + } +} + +// "typeName is a (pointer to a)^'typePtrLevel' GC type because it contains a field +// named 'child' of type 'why' (or pointer to 'why' if fieldPtrLevel == 1), which is +// itself a GCThing or GCPointer." +function markGCType(typeName, child, why, typePtrLevel, fieldPtrLevel, indent) +{ + // Some types, like UniquePtr, do not mark/trace/relocate their contained + // pointers and so should not hold them live across a GC. UniquePtr in + // particular should be the only thing pointing to a structure containing a + // GCPointer, so nothing else can possibly trace it and it'll die when the + // UniquePtr goes out of scope. So we say that memory pointed to by a + // UniquePtr is just as unsafe as the stack for storing GC pointers. + if (!fieldPtrLevel && isUnsafeStorage(typeName)) { + // The UniquePtr itself is on the stack but when you dereference the + // contained pointer, you get to the unsafe memory that we are treating + // as if it were the stack (aka ptrLevel 0). Note that + // UniquePtr<UniquePtr<JSObject*>> is fine, so we don't want to just + // hardcode the ptrLevel. + fieldPtrLevel = -1; + } + + // Example: with: + // struct Pair { JSObject* foo; int bar; }; + // struct { Pair** info }*** + // make a call to: + // child='info' typePtrLevel=3 fieldPtrLevel=2 + // for a final ptrLevel of 5, used to later call: + // child='foo' typePtrLevel=5 fieldPtrLevel=1 + // + var ptrLevel = typePtrLevel + fieldPtrLevel; + + // ...except when > 2 levels of pointers away from an actual GC thing, stop + // searching the graph. (This would just be > 1, except that a UniquePtr + // field might still have a GC pointer.) + if (ptrLevel > 2) + return; + + if (isRootedGCPointerTypeName(typeName) && !(typeName in typeInfo.RootedPointers)) + printErr("FIXME: use in-source annotation for " + typeName); + + if (ptrLevel == 0 && (typeName in typeInfo.RootedGCThings)) + return; + if (ptrLevel == 1 && (isRootedGCPointerTypeName(typeName) || (typeName in typeInfo.RootedPointers))) + return; + + if (ptrLevel == 0) { + if (typeName in typeInfo.NonGCTypes) + return; + if (!(typeName in gcTypes)) + gcTypes[typeName] = new Set(); + gcTypes[typeName].add(why); + } else if (ptrLevel == 1) { + if (typeName in typeInfo.NonGCPointers) + return; + if (!(typeName in gcPointers)) + gcPointers[typeName] = new Set(); + gcPointers[typeName].add(why); + } + + if (ptrLevel < 2) { + if (!gcFields.has(typeName)) + gcFields.set(typeName, new Map()); + gcFields.get(typeName).set(child, [ why, fieldPtrLevel ]); + } + + if (typeName in structureParents) { + for (var field of structureParents[typeName]) { + var [ holderType, fieldName ] = field; + markGCType(holderType, fieldName, typeName, ptrLevel, 0, indent + " "); + } + } + if (typeName in pointerParents) { + for (var field of pointerParents[typeName]) { + var [ holderType, fieldName ] = field; + markGCType(holderType, fieldName, typeName, ptrLevel, 1, indent + " "); + } + } +} + +function addGCType(typeName, child, why, depth, fieldPtrLevel) +{ + pendingGCTypes.push([typeName, '<annotation>', '(annotation)', 0, 0]); +} + +function addGCPointer(typeName) +{ + pendingGCTypes.push([typeName, '<pointer-annotation>', '(annotation)', 1, 0]); +} + +for (const pending of pendingGCTypes) { + markGCType(...pending); +} + +// Call a function for a type and every type that contains the type in a field +// or as a base class (which internally is pretty much the same thing -- +// subclasses are structs beginning with the base class and adding on their +// local fields.) +function foreachContainingStruct(typeName, func, seen = new Set()) +{ + function recurse(container, typeName) { + if (seen.has(typeName)) + return; + seen.add(typeName); + + func(container, typeName); + + if (typeName in subClasses) { + for (const sub of subClasses[typeName]) + recurse("subclass of " + typeName, sub); + } + if (typeName in structureParents) { + for (const [holder, field] of structureParents[typeName]) + recurse(field + " : " + typeName, holder); + } + } + + recurse('<annotation>', typeName); +} + +for (var type of listNonGCPointers()) + typeInfo.NonGCPointers[type] = true; + +function explain(csu, indent, seen) { + if (!seen) + seen = new Set(); + seen.add(csu); + if (!gcFields.has(csu)) + return; + var fields = gcFields.get(csu); + + if (fields.has('<annotation>')) { + print(indent + "which is annotated as a GCThing"); + return; + } + if (fields.has('<pointer-annotation>')) { + print(indent + "which is annotated as a GCPointer"); + return; + } + for (var [ field, [ child, ptrdness ] ] of fields) { + var msg = indent; + if (field[0] == '<') + msg += "inherits from "; + else { + if (field.startsWith("template-param-")) { + msg += "inherits annotations from template parameter '" + field.substr(15) + "' "; + } else { + msg += "contains field '" + field + "' "; + } + if (ptrdness == -1) + msg += "(with a pointer to unsafe storage) holding a "; + else if (ptrdness == 0) + msg += "of type "; + else + msg += "pointing to type "; + } + msg += child; + print(msg); + if (!seen.has(child)) + explain(child, indent + " ", seen); + } +} + +var origOut = os.file.redirect(options.gcTypes); + +for (var csu in gcTypes) { + print("GCThing: " + csu); + explain(csu, " "); +} +for (var csu in gcPointers) { + print("GCPointer: " + csu); + explain(csu, " "); +} + +// Redirect output to the typeInfo file and close the gcTypes file. +os.file.close(os.file.redirect(options.typeInfo)); + +// Compute the set of types that suppress GC within their RAII scopes (eg +// AutoSuppressGC, AutoSuppressGCForAnalysis). +var seen = new Set(); +for (let csu in typeInfo.GCSuppressors) + foreachContainingStruct(csu, + (holder, typeName) => { typeInfo.GCSuppressors[typeName] = holder }, + seen); + +print(JSON.stringify(typeInfo, null, 4)); + +os.file.close(os.file.redirect(origOut)); |