diff options
Diffstat (limited to 'js/src/devtools/rootAnalysis/analyzeHeapWrites.js')
| -rw-r--r-- | js/src/devtools/rootAnalysis/analyzeHeapWrites.js | 1398 |
1 files changed, 1398 insertions, 0 deletions
diff --git a/js/src/devtools/rootAnalysis/analyzeHeapWrites.js b/js/src/devtools/rootAnalysis/analyzeHeapWrites.js new file mode 100644 index 0000000000..fdb9eaffb8 --- /dev/null +++ b/js/src/devtools/rootAnalysis/analyzeHeapWrites.js @@ -0,0 +1,1398 @@ +/* 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'); +loadRelativeToScript('callgraph.js'); +loadRelativeToScript('dumpCFG.js'); + +/////////////////////////////////////////////////////////////////////////////// +// Annotations +/////////////////////////////////////////////////////////////////////////////// + +function checkExternalFunction(entry) +{ + var whitelist = [ + "__builtin_clz", + "__builtin_expect", + "isprint", + "ceilf", + "floorf", + /^rusturl/, + "memcmp", + "strcmp", + "fmod", + "floor", + "ceil", + "atof", + /memchr/, + "strlen", + /Servo_DeclarationBlock_GetCssText/, + "Servo_GetArcStringData", + "Servo_IsWorkerThread", + /nsIFrame::AppendOwnedAnonBoxes/, + // Assume that atomic accesses are threadsafe. + /^__atomic_/, + ]; + if (entry.matches(whitelist)) + return; + + // memcpy and memset are safe if the target pointer is threadsafe. + const simpleWrites = [ + "memcpy", + "memset", + "memmove", + ]; + + if (entry.isSafeArgument(1) && simpleWrites.includes(entry.name)) + return; + + dumpError(entry, null, "External function"); +} + +function hasThreadsafeReferenceCounts(entry, regexp) +{ + // regexp should match some nsISupports-operating function and produce the + // name of the nsISupports class via exec(). + + // nsISupports classes which have threadsafe reference counting. + var whitelist = [ + "nsIRunnable", + + // I don't know if these always have threadsafe refcounts. + "nsAtom", + "nsIPermissionManager", + "nsIURI", + ]; + + var match = regexp.exec(entry.name); + return match && nameMatchesArray(match[1], whitelist); +} + +function checkOverridableVirtualCall(entry, location, callee) +{ + // We get here when a virtual call is made on a structure which might be + // overridden by script or by a binary extension. This includes almost + // everything under nsISupports, however, so for the most part we ignore + // this issue. The exception is for nsISupports AddRef/Release, which are + // not in general threadsafe and whose overrides will not be generated by + // the callgraph analysis. + if (callee != "nsISupports.AddRef" && callee != "nsISupports.Release") + return; + + if (hasThreadsafeReferenceCounts(entry, /::~?nsCOMPtr\(.*?\[with T = (.*?)\]$/)) + return; + if (hasThreadsafeReferenceCounts(entry, /RefPtrTraits.*?::Release.*?\[with U = (.*?)\]/)) + return; + if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::assign_assuming_AddRef.*?\[with T = (.*?)\]/)) + return; + if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::assign_with_AddRef.*?\[with T = (.*?)\]/)) + return; + + // Watch for raw addref/release. + var whitelist = [ + "Gecko_AddRefAtom", + "Gecko_ReleaseAtom", + /nsPrincipal::Get/, + /CounterStylePtr::Reset/, + ]; + if (entry.matches(whitelist)) + return; + + dumpError(entry, location, "AddRef/Release on nsISupports"); +} + +function checkIndirectCall(entry, location, callee) +{ + var name = entry.name; + + // These hash table callbacks should be threadsafe. + if (/PLDHashTable/.test(name) && (/matchEntry/.test(callee) || /hashKey/.test(callee))) + return; + if (/PL_HashTable/.test(name) && /keyCompare/.test(callee)) + return; + + dumpError(entry, location, "Indirect call " + callee); +} + +function checkVariableAssignment(entry, location, variable) +{ + var name = entry.name; + + dumpError(entry, location, "Variable assignment " + variable); +} + +// Annotations for function parameters, based on function name and parameter +// name + type. +function treatAsSafeArgument(entry, varName, csuName) +{ + var whitelist = [ + // These iterator classes should all be thread local. They are passed + // in to some Servo bindings and are created on the heap by others, so + // just ignore writes to them. + [null, null, /StyleChildrenIterator/], + [null, null, /ExplicitChildIterator/], + + // The use of BeginReading() to instantiate this class confuses the + // analysis. + [null, null, /nsReadingIterator/], + + // These classes are passed to some Servo bindings to fill in. + [/^Gecko_/, null, "nsStyleImageLayers"], + [/^Gecko_/, null, /FontFamilyList/], + + // Various Servo binding out parameters. This is a mess and there needs + // to be a way to indicate which params are out parameters, either using + // an attribute or a naming convention. + ["Gecko_CopyAnimationNames", "aDest", null], + ["Gecko_SetAnimationName", "aStyleAnimation", null], + ["Gecko_SetCounterStyleToName", "aPtr", null], + ["Gecko_SetCounterStyleToSymbols", "aPtr", null], + ["Gecko_SetCounterStyleToString", "aPtr", null], + ["Gecko_CopyCounterStyle", "aDst", null], + ["Gecko_SetMozBinding", "aDisplay", null], + [/ClassOrClassList/, /aClass/, null], + ["Gecko_GetAtomAsUTF16", "aLength", null], + ["Gecko_CopyMozBindingFrom", "aDest", null], + ["Gecko_SetNullImageValue", "aImage", null], + ["Gecko_SetGradientImageValue", "aImage", null], + ["Gecko_SetImageElement", "aImage", null], + ["Gecko_SetLayerImageImageValue", "aImage", null], + ["Gecko_CopyImageValueFrom", "aImage", null], + ["Gecko_SetCursorArrayLength", "aStyleUI", null], + ["Gecko_CopyCursorArrayFrom", "aDest", null], + ["Gecko_SetCursorImageValue", "aCursor", null], + ["Gecko_SetListStyleImageImageValue", "aList", null], + ["Gecko_SetListStyleImageNone", "aList", null], + ["Gecko_CopyListStyleImageFrom", "aList", null], + ["Gecko_ClearStyleContents", "aContent", null], + ["Gecko_CopyStyleContentsFrom", "aContent", null], + ["Gecko_CopyStyleGridTemplateValues", "aGridTemplate", null], + ["Gecko_ResetStyleCoord", null, null], + ["Gecko_CopyClipPathValueFrom", "aDst", null], + ["Gecko_DestroyClipPath", "aClip", null], + ["Gecko_ResetFilters", "effects", null], + [/Gecko_CSSValue_Set/, "aCSSValue", null], + ["Gecko_CSSValue_Drop", "aCSSValue", null], + ["Gecko_CSSFontFaceRule_GetCssText", "aResult", null], + ["Gecko_EnsureTArrayCapacity", "aArray", null], + ["Gecko_ClearPODTArray", "aArray", null], + ["Gecko_SetStyleGridTemplate", "aGridTemplate", null], + ["Gecko_ResizeTArrayForStrings", "aArray", null], + ["Gecko_ClearAndResizeStyleContents", "aContent", null], + [/Gecko_ClearAndResizeCounter/, "aContent", null], + [/Gecko_CopyCounter.*?From/, "aContent", null], + [/Gecko_SetContentDataImageValue/, "aList", null], + [/Gecko_SetContentData/, "aContent", null], + ["Gecko_SetCounterFunction", "aContent", null], + [/Gecko_EnsureStyle.*?ArrayLength/, "aArray", null], + ["Gecko_GetOrCreateKeyframeAtStart", "aKeyframes", null], + ["Gecko_GetOrCreateInitialKeyframe", "aKeyframes", null], + ["Gecko_GetOrCreateFinalKeyframe", "aKeyframes", null], + ["Gecko_AppendPropertyValuePair", "aProperties", null], + ["Gecko_SetStyleCoordCalcValue", null, null], + ["Gecko_StyleClipPath_SetURLValue", "aClip", null], + ["Gecko_nsStyleFilter_SetURLValue", "aEffects", null], + ["Gecko_nsStyleSVG_SetDashArrayLength", "aSvg", null], + ["Gecko_nsStyleSVG_CopyDashArray", "aDst", null], + ["Gecko_nsStyleFont_SetLang", "aFont", null], + ["Gecko_nsStyleFont_CopyLangFrom", "aFont", null], + ["Gecko_ClearWillChange", "aDisplay", null], + ["Gecko_AppendWillChange", "aDisplay", null], + ["Gecko_CopyWillChangeFrom", "aDest", null], + ["Gecko_InitializeImageCropRect", "aImage", null], + ["Gecko_CopyShapeSourceFrom", "aDst", null], + ["Gecko_DestroyShapeSource", "aShape", null], + ["Gecko_StyleShapeSource_SetURLValue", "aShape", null], + ["Gecko_NewBasicShape", "aShape", null], + ["Gecko_NewShapeImage", "aShape", null], + ["Gecko_nsFont_InitSystem", "aDest", null], + ["Gecko_nsFont_SetFontFeatureValuesLookup", "aFont", null], + ["Gecko_nsFont_ResetFontFeatureValuesLookup", "aFont", null], + ["Gecko_nsStyleFont_FixupNoneGeneric", "aFont", null], + ["Gecko_StyleTransition_SetUnsupportedProperty", "aTransition", null], + ["Gecko_AddPropertyToSet", "aPropertySet", null], + ["Gecko_CalcStyleDifference", "aAnyStyleChanged", null], + ["Gecko_CalcStyleDifference", "aOnlyResetStructsChanged", null], + ["Gecko_nsStyleSVG_CopyContextProperties", "aDst", null], + ["Gecko_nsStyleFont_PrefillDefaultForGeneric", "aFont", null], + ["Gecko_nsStyleSVG_SetContextPropertiesLength", "aSvg", null], + ["Gecko_ClearAlternateValues", "aFont", null], + ["Gecko_AppendAlternateValues", "aFont", null], + ["Gecko_CopyAlternateValuesFrom", "aDest", null], + ["Gecko_CounterStyle_GetName", "aResult", null], + ["Gecko_CounterStyle_GetSingleString", "aResult", null], + ["Gecko_nsTArray_FontFamilyName_AppendNamed", "aNames", null], + ["Gecko_nsTArray_FontFamilyName_AppendGeneric", "aNames", null], + ]; + for (var [entryMatch, varMatch, csuMatch] of whitelist) { + assert(entryMatch || varMatch || csuMatch); + if (entryMatch && !nameMatches(entry.name, entryMatch)) + continue; + if (varMatch && !nameMatches(varName, varMatch)) + continue; + if (csuMatch && (!csuName || !nameMatches(csuName, csuMatch))) + continue; + return true; + } + return false; +} + +function isSafeAssignment(entry, edge, variable) +{ + if (edge.Kind != 'Assign') + return false; + + var [mangled, unmangled] = splitFunction(entry.name); + + // The assignment + // + // nsFont* font = fontTypes[eType]; + // + // ends up with 'font' pointing to a member of 'this', so it should inherit + // the safety of 'this'. + if (unmangled.includes("mozilla::LangGroupFontPrefs::Initialize") && + variable == 'font') + { + const [lhs, rhs] = edge.Exp; + const {Kind, Exp: [{Kind: indexKind, Exp: [collection, index]}]} = rhs; + if (Kind == 'Drf' && + indexKind == 'Index' && + collection.Kind == 'Var' && + collection.Variable.Name[0] == 'fontTypes') + { + return entry.isSafeArgument(0); // 'this' + } + } + + return false; +} + +function checkFieldWrite(entry, location, fields) +{ + var name = entry.name; + for (var field of fields) { + // The analysis is having some trouble keeping track of whether + // already_AddRefed and nsCOMPtr structures are safe to access. + // Hopefully these will be thread local, but it would be better to + // improve the analysis to handle these. + if (/already_AddRefed.*?.mRawPtr/.test(field)) + return; + if (/nsCOMPtr<.*?>.mRawPtr/.test(field)) + return; + + if (/\bThreadLocal<\b/.test(field)) + return; + + // Debugging check for string corruption. + if (field == "nsStringBuffer.mCanary") + return; + } + + var str = ""; + for (var field of fields) + str += " " + field; + + dumpError(entry, location, "Field write" + str); +} + +function checkDereferenceWrite(entry, location, variable) +{ + var name = entry.name; + + // Maybe<T> uses placement new on local storage in a way we don't understand. + // Allow this if the Maybe<> value itself is threadsafe. + if (/Maybe.*?::emplace/.test(name) && entry.isSafeArgument(0)) + return; + + // UniquePtr writes through temporaries referring to its internal storage. + // Allow this if the UniquePtr<> is threadsafe. + if (/UniquePtr.*?::reset/.test(name) && entry.isSafeArgument(0)) + return; + + // Operations on nsISupports reference counts. + if (hasThreadsafeReferenceCounts(entry, /nsCOMPtr<T>::swap\(.*?\[with T = (.*?)\]/)) + return; + + // ConvertToLowerCase::write writes through a local pointer into the first + // argument. + if (/ConvertToLowerCase::write/.test(name) && entry.isSafeArgument(0)) + return; + + dumpError(entry, location, "Dereference write " + (variable ? variable : "<unknown>")); +} + +function ignoreCallEdge(entry, callee) +{ + var name = entry.name; + + // nsPropertyTable::GetPropertyInternal has the option of removing data + // from the table, but when it is called by nsPropertyTable::GetProperty + // this will not occur. + if (/nsPropertyTable::GetPropertyInternal/.test(callee) && + /nsPropertyTable::GetProperty/.test(name)) + { + return true; + } + + // Document::PropertyTable calls GetExtraPropertyTable (which has side + // effects) if the input category is non-zero. If a literal zero was passed + // in for the category then we treat it as a safe argument, per + // isEdgeSafeArgument, so just watch for that. + if (/Document::GetExtraPropertyTable/.test(callee) && + /Document::PropertyTable/.test(name) && + entry.isSafeArgument(1)) + { + return true; + } + + // This function has an explicit test for being on the main thread if the + // style has non-threadsafe refcounts, but the analysis isn't smart enough + // to understand what the actual styles that can be involved are. + if (/nsStyleList::SetCounterStyle/.test(callee)) + return true; + + // CachedBorderImageData is exclusively owned by nsStyleImage, but the + // analysis is not smart enough to know this. + if (/CachedBorderImageData::PurgeCachedImages/.test(callee) && + /nsStyleImage::/.test(name) && + entry.isSafeArgument(0)) + { + return true; + } + + // StyleShapeSource exclusively owns its UniquePtr<nsStyleImage>. + if (/nsStyleImage::SetURLValue/.test(callee) && + /StyleShapeSource::SetURL/.test(name) && + entry.isSafeArgument(0)) + { + return true; + } + + // The AddRef through a just-assigned heap pointer here is not handled by + // the analysis. + if (/nsCSSValue::Array::AddRef/.test(callee) && + /nsStyleContentData::SetCounters/.test(name) && + entry.isSafeArgument(2)) + { + return true; + } + + // AllChildrenIterator asks AppendOwnedAnonBoxes to append into an nsTArray + // local variable. + if (/nsIFrame::AppendOwnedAnonBoxes/.test(callee) && + /AllChildrenIterator::AppendNativeAnonymousChildren/.test(name)) + { + return true; + } + + // Runnables are created and named on one thread, then dispatched + // (possibly to another). Writes on the origin thread are ok. + if (/::SetName/.test(callee) && + /::UnlabeledDispatch/.test(name)) + { + return true; + } + + // We manually lock here + if (name == "Gecko_nsFont_InitSystem" || + name == "Gecko_GetFontMetrics" || + name == "Gecko_nsStyleFont_FixupMinFontSize" || + /ThreadSafeGetDefaultFontHelper/.test(name)) + { + return true; + } + + return false; +} + +function ignoreContents(entry) +{ + var whitelist = [ + // We don't care what happens when we're about to crash. + "abort", + /MOZ_ReportAssertionFailure/, + /MOZ_ReportCrash/, + /MOZ_Crash/, + /MOZ_CrashPrintf/, + /AnnotateMozCrashReason/, + /InvalidArrayIndex_CRASH/, + /NS_ABORT_OOM/, + + // These ought to be threadsafe. + "NS_DebugBreak", + /mozalloc_handle_oom/, + /^NS_Log/, /log_print/, /LazyLogModule::operator/, + /SprintfLiteral/, "PR_smprintf", "PR_smprintf_free", + /NS_DispatchToMainThread/, /NS_ReleaseOnMainThread/, + /NS_NewRunnableFunction/, /NS_Atomize/, + /nsCSSValue::BufferFromString/, + /NS_xstrdup/, + /Assert_NoQueryNeeded/, + /AssertCurrentThreadOwnsMe/, + /PlatformThread::CurrentId/, + /imgRequestProxy::GetProgressTracker/, // Uses an AutoLock + /Smprintf/, + "malloc", + "calloc", + "free", + "realloc", + "memalign", + "strdup", + "strndup", + "moz_xmalloc", + "moz_xcalloc", + "moz_xrealloc", + "moz_xmemalign", + "moz_xstrdup", + "moz_xstrndup", + "jemalloc_thread_local_arena", + + // These all create static strings in local storage, which is threadsafe + // to do but not understood by the analysis yet. + / EmptyString\(\)/, + + // These could probably be handled by treating the scope of PSAutoLock + // aka BaseAutoLock<PSMutex> as threadsafe. + /profiler_register_thread/, + /profiler_unregister_thread/, + + // The analysis thinks we'll write to mBits in the DoGetStyleFoo<false> + // call. Maybe the template parameter confuses it? + /ComputedStyle::PeekStyle/, + + // The analysis can't cope with the indirection used for the objects + // being initialized here, from nsCSSValue::Array::Create to the return + // value of the Item(i) getter. + /nsCSSValue::SetCalcValue/, + + // Unable to analyze safety of linked list initialization. + "Gecko_NewCSSValueSharedList", + "Gecko_CSSValue_InitSharedList", + + // Unable to trace through dataflow, but straightforward if inspected. + "Gecko_NewNoneTransform", + + // Need main thread assertions or other fixes. + /EffectCompositor::GetServoAnimationRule/, + ]; + if (entry.matches(whitelist)) + return true; + + if (entry.isSafeArgument(0)) { + var heapWhitelist = [ + // Operations on heap structures pointed to by arrays and strings are + // threadsafe as long as the array/string itself is threadsafe. + /nsTArray_Impl.*?::AppendElement/, + /nsTArray_Impl.*?::RemoveElementsAt/, + /nsTArray_Impl.*?::ReplaceElementsAt/, + /nsTArray_Impl.*?::InsertElementAt/, + /nsTArray_Impl.*?::SetCapacity/, + /nsTArray_Impl.*?::SetLength/, + /nsTArray_base.*?::EnsureCapacity/, + /nsTArray_base.*?::ShiftData/, + /AutoTArray.*?::Init/, + /(nsTSubstring<T>|nsAC?String)::SetCapacity/, + /(nsTSubstring<T>|nsAC?String)::SetLength/, + /(nsTSubstring<T>|nsAC?String)::Assign/, + /(nsTSubstring<T>|nsAC?String)::Append/, + /(nsTSubstring<T>|nsAC?String)::Replace/, + /(nsTSubstring<T>|nsAC?String)::Trim/, + /(nsTSubstring<T>|nsAC?String)::Truncate/, + /(nsTSubstring<T>|nsAC?String)::StripTaggedASCII/, + /(nsTSubstring<T>|nsAC?String)::operator=/, + /nsTAutoStringN<T, N>::nsTAutoStringN/, + + // Similar for some other data structures + /nsCOMArray_base::SetCapacity/, + /nsCOMArray_base::Clear/, + /nsCOMArray_base::AppendElement/, + + // UniquePtr is similar. + /mozilla::UniquePtr/, + + // The use of unique pointers when copying mCropRect here confuses + // the analysis. + /nsStyleImage::DoCopy/, + ]; + if (entry.matches(heapWhitelist)) + return true; + } + + if (entry.isSafeArgument(1)) { + var firstArgWhitelist = [ + /nsTextFormatter::snprintf/, + /nsTextFormatter::ssprintf/, + /_ASCIIToUpperInSitu/, + + // Handle some writes into an array whose safety we don't have a good way + // of tracking currently. + /FillImageLayerList/, + /FillImageLayerPositionCoordList/, + ]; + if (entry.matches(firstArgWhitelist)) + return true; + } + + if (entry.isSafeArgument(2)) { + var secondArgWhitelist = [ + /nsStringBuffer::ToString/, + /AppendUTF\d+toUTF\d+/, + /AppendASCIItoUTF\d+/, + ]; + if (entry.matches(secondArgWhitelist)) + return true; + } + + return false; +} + +/////////////////////////////////////////////////////////////////////////////// +// Sixgill Utilities +/////////////////////////////////////////////////////////////////////////////// + +function variableName(variable) +{ + return (variable && variable.Name) ? variable.Name[0] : null; +} + +function stripFields(exp) +{ + // Fields and index operations do not involve any dereferences. Remove them + // from the expression but remember any encountered fields for use by + // annotations later on. + var fields = []; + while (true) { + if (exp.Kind == "Index") { + exp = exp.Exp[0]; + continue; + } + if (exp.Kind == "Fld") { + var csuName = exp.Field.FieldCSU.Type.Name; + var fieldName = exp.Field.Name[0]; + assert(csuName && fieldName); + fields.push(csuName + "." + fieldName); + exp = exp.Exp[0]; + continue; + } + break; + } + return [exp, fields]; +} + +function isLocalVariable(variable) +{ + switch (variable.Kind) { + case "Return": + case "Temp": + case "Local": + case "Arg": + return true; + } + return false; +} + +function isDirectCall(edge, regexp) +{ + return edge.Kind == "Call" + && edge.Exp[0].Kind == "Var" + && regexp.test(variableName(edge.Exp[0].Variable)); +} + +function isZero(exp) +{ + return exp.Kind == "Int" && exp.String == "0"; +} + +/////////////////////////////////////////////////////////////////////////////// +// Analysis Structures +/////////////////////////////////////////////////////////////////////////////// + +// Safe arguments are those which may be written through (directly, not through +// pointer fields etc.) without concerns about thread safety. This includes +// pointers to stack data, null pointers, and other data we know is thread +// local, such as certain arguments to the root functions. +// +// Entries in the worklist keep track of the pointer arguments to the function +// which are safe using a sorted array, so that this can be propagated down the +// stack. Zero is |this|, and arguments are indexed starting at one. + +function WorklistEntry(name, safeArguments, stack, parameterNames) +{ + this.name = name; + this.safeArguments = safeArguments; + this.stack = stack; + this.parameterNames = parameterNames; +} + +WorklistEntry.prototype.readable = function() +{ + const [ mangled, readable ] = splitFunction(this.name); + return readable; +} + +WorklistEntry.prototype.mangledName = function() +{ + var str = this.name; + for (var safe of this.safeArguments) + str += " SAFE " + safe; + return str; +} + +WorklistEntry.prototype.isSafeArgument = function(index) +{ + for (var safe of this.safeArguments) { + if (index == safe) + return true; + } + return false; +} + +WorklistEntry.prototype.setParameterName = function(index, name) +{ + this.parameterNames[index] = name; +} + +WorklistEntry.prototype.addSafeArgument = function(index) +{ + if (this.isSafeArgument(index)) + return; + this.safeArguments.push(index); + + // Sorting isn't necessary for correctness but makes printed stack info tidier. + this.safeArguments.sort(); +} + +function safeArgumentIndex(variable) +{ + if (variable.Kind == "This") + return 0; + if (variable.Kind == "Arg") + return variable.Index + 1; + return -1; +} + +function nameMatches(name, match) +{ + if (typeof match == "string") { + if (name == match) + return true; + } else { + assert(match instanceof RegExp); + if (match.test(name)) + return true; + } + return false; +} + +function nameMatchesArray(name, matchArray) +{ + for (var match of matchArray) { + if (nameMatches(name, match)) + return true; + } + return false; +} + +WorklistEntry.prototype.matches = function(matchArray) +{ + return nameMatchesArray(this.name, matchArray); +} + +function CallSite(callee, safeArguments, location, parameterNames) +{ + this.callee = callee; + this.safeArguments = safeArguments; + this.location = location; + this.parameterNames = parameterNames; +} + +CallSite.prototype.safeString = function() +{ + if (this.safeArguments.length) { + var str = ""; + for (var i = 0; i < this.safeArguments.length; i++) { + var arg = this.safeArguments[i]; + if (arg in this.parameterNames) + str += " " + this.parameterNames[arg]; + else + str += " <" + ((arg == 0) ? "this" : "arg" + (arg - 1)) + ">"; + } + return " ### SafeArguments:" + str; + } + return ""; +} + +/////////////////////////////////////////////////////////////////////////////// +// Analysis Core +/////////////////////////////////////////////////////////////////////////////// + +var errorCount = 0; +var errorLimit = 100; + +// We want to suppress output for functions that ended up not having any +// hazards, for brevity of the final output. So each new toplevel function will +// initialize this to a string, which should be printed only if an error is +// seen. +var errorHeader; + +var startTime = new Date; +function elapsedTime() +{ + var seconds = (new Date - startTime) / 1000; + return "[" + seconds.toFixed(2) + "s] "; +} + +var options = parse_options([ + { + name: '--strip-prefix', + default: os.getenv('SOURCE') || '', + type: 'string' + }, + { + name: '--add-prefix', + default: os.getenv('URLPREFIX') || '', + type: 'string' + }, + { + name: '--verbose', + type: 'bool' + }, +]); + +function add_trailing_slash(str) { + if (str == '') + return str; + return str.endsWith("/") ? str : str + "/"; +} + +var removePrefix = add_trailing_slash(options.strip_prefix); +var addPrefix = add_trailing_slash(options.add_prefix); + +if (options.verbose) { + printErr(`Removing prefix ${removePrefix} from paths`); + printErr(`Prepending ${addPrefix} to paths`); +} + +print(elapsedTime() + "Loading types..."); +if (os.getenv("TYPECACHE")) + loadTypesWithCache('src_comp.xdb', os.getenv("TYPECACHE")); +else + loadTypes('src_comp.xdb'); +print(elapsedTime() + "Starting analysis..."); + +var xdb = xdbLibrary(); +xdb.open("src_body.xdb"); + +var minStream = xdb.min_data_stream(); +var maxStream = xdb.max_data_stream(); +var roots = []; + +var [flag, arg] = scriptArgs; +if (flag && (flag == '-f' || flag == '--function')) { + roots = [arg]; +} else { + for (var bodyIndex = minStream; bodyIndex <= maxStream; bodyIndex++) { + var key = xdb.read_key(bodyIndex); + var name = key.readString(); + if (/^Gecko_/.test(name)) { + var data = xdb.read_entry(key); + if (/ServoBindings.cpp/.test(data.readString())) + roots.push(name); + xdb.free_string(data); + } + xdb.free_string(key); + } +} + +print(elapsedTime() + "Found " + roots.length + " roots."); +for (var i = 0; i < roots.length; i++) { + var root = roots[i]; + errorHeader = elapsedTime() + "#" + (i + 1) + " Analyzing " + root + " ..."; + try { + processRoot(root); + } catch (e) { + if (e != "Error!") + throw e; + } +} + +print(`${elapsedTime()}Completed analysis, found ${errorCount}/${errorLimit} allowed errors`); + +var currentBody; + +// All local variable assignments we have seen in either the outer or inner +// function. This crosses loop boundaries, and currently has an unsoundness +// where later assignments in a loop are not taken into account. +var assignments; + +// All loops in the current function which are reachable off main thread. +var reachableLoops; + +// Functions that are reachable from the current root. +var reachable = {}; + +function dumpError(entry, location, text) +{ + if (errorHeader) { + print(errorHeader); + errorHeader = undefined; + } + + var stack = entry.stack; + print("Error: " + text); + print("Location: " + entry.name + (location ? " @ " + location : "") + stack[0].safeString()); + print("Stack Trace:"); + // Include the callers in the stack trace instead of the callees. Make sure + // the dummy stack entry we added for the original roots is in place. + assert(stack[stack.length - 1].location == null); + for (var i = 0; i < stack.length - 1; i++) + print(stack[i + 1].callee + " @ " + stack[i].location + stack[i + 1].safeString()); + print("\n"); + + if (++errorCount == errorLimit) { + print("Maximum number of errors encountered, exiting..."); + quit(); + } + + throw "Error!"; +} + +// If edge is an assignment from a local variable, return the rhs variable. +function variableAssignRhs(edge) +{ + if (edge.Kind == "Assign" && edge.Exp[1].Kind == "Drf" && edge.Exp[1].Exp[0].Kind == "Var") { + var variable = edge.Exp[1].Exp[0].Variable; + if (isLocalVariable(variable)) + return variable; + } + return null; +} + +function processAssign(body, entry, location, lhs, edge) +{ + var fields; + [lhs, fields] = stripFields(lhs); + + switch (lhs.Kind) { + case "Var": + var name = variableName(lhs.Variable); + if (isLocalVariable(lhs.Variable)) { + // Remember any assignments to local variables in this function. + // Note that we ignore any points where the variable's address is + // taken and indirect assignments might occur. This is an + // unsoundness in the analysis. + + let assign = [body, edge]; + + // Chain assignments if the RHS has only been assigned once. + var rhsVariable = variableAssignRhs(edge); + if (rhsVariable) { + var rhsAssign = singleAssignment(variableName(rhsVariable)); + if (rhsAssign) + assign = rhsAssign; + } + + if (!(name in assignments)) + assignments[name] = []; + assignments[name].push(assign); + } else { + checkVariableAssignment(entry, location, name); + } + return; + case "Drf": + var variable = null; + if (lhs.Exp[0].Kind == "Var") { + variable = lhs.Exp[0].Variable; + if (isSafeVariable(entry, variable)) + return; + } else if (lhs.Exp[0].Kind == "Fld") { + const { + Name: [ fieldName ], + Type: {Kind, Type: fieldType}, + FieldCSU: {Type: {Kind: containerTypeKind, + Name: containerTypeName}} + } = lhs.Exp[0].Field; + const [containerExpr] = lhs.Exp[0].Exp; + + if (containerTypeKind == 'CSU' && + Kind == 'Pointer' && + isEdgeSafeArgument(entry, containerExpr) && + isSafeMemberPointer(containerTypeName, fieldName, fieldType)) + { + return; + } + } + if (fields.length) + checkFieldWrite(entry, location, fields); + else + checkDereferenceWrite(entry, location, variableName(variable)); + return; + case "Int": + if (isZero(lhs)) { + // This shows up under MOZ_ASSERT, to crash the process. + return; + } + } + dumpError(entry, location, "Unknown assignment " + JSON.stringify(lhs)); +} + +function get_location(rawLocation) { + const filename = rawLocation.CacheString.replace(removePrefix, ''); + return addPrefix + filename + "#" + rawLocation.Line; +} + +function process(entry, body, addCallee) +{ + if (!("PEdge" in body)) + return; + + // Add any arguments which are safe due to annotations. + if ("DefineVariable" in body) { + for (var defvar of body.DefineVariable) { + var index = safeArgumentIndex(defvar.Variable); + if (index >= 0) { + var varName = index ? variableName(defvar.Variable) : "this"; + assert(varName); + entry.setParameterName(index, varName); + var csuName = null; + var type = defvar.Type; + if (type.Kind == "Pointer" && type.Type.Kind == "CSU") + csuName = type.Type.Name; + if (treatAsSafeArgument(entry, varName, csuName)) + entry.addSafeArgument(index); + } + } + } + + // Points in the body which are reachable if we are not on the main thread. + var nonMainThreadPoints = []; + nonMainThreadPoints[body.Index[0]] = true; + + for (var edge of body.PEdge) { + // Ignore code that only executes on the main thread. + if (!(edge.Index[0] in nonMainThreadPoints)) + continue; + + var location = get_location(body.PPoint[edge.Index[0] - 1].Location); + + var callees = getCallees(edge); + for (var callee of callees) { + switch (callee.kind) { + case "direct": + var safeArguments = getEdgeSafeArguments(entry, edge, callee.name); + addCallee(new CallSite(callee.name, safeArguments, location, {})); + break; + case "resolved-field": + break; + case "field": + var field = callee.csu + "." + callee.field; + if (callee.isVirtual) + checkOverridableVirtualCall(entry, location, field); + else + checkIndirectCall(entry, location, field); + break; + case "indirect": + checkIndirectCall(entry, location, callee.variable); + break; + default: + dumpError(entry, location, "Unknown call " + callee.kind); + break; + } + } + + var fallthrough = true; + + if (edge.Kind == "Assign") { + assert(edge.Exp.length == 2); + processAssign(body, entry, location, edge.Exp[0], edge); + } else if (edge.Kind == "Call") { + assert(edge.Exp.length <= 2); + if (edge.Exp.length == 2) + processAssign(body, entry, location, edge.Exp[1], edge); + + // Treat assertion failures as if they don't return, so that + // asserting NS_IsMainThread() is sufficient to prevent the + // analysis from considering a block of code. + if (isDirectCall(edge, /MOZ_ReportAssertionFailure/)) + fallthrough = false; + } else if (edge.Kind == "Loop") { + reachableLoops[edge.BlockId.Loop] = true; + } else if (edge.Kind == "Assume") { + if (testFailsOffMainThread(edge.Exp[0], edge.PEdgeAssumeNonZero)) + fallthrough = false; + } + + if (fallthrough) + nonMainThreadPoints[edge.Index[1]] = true; + } +} + +function maybeProcessMissingFunction(entry, addCallee) +{ + // If a function is missing it might be because a destructor Foo::~Foo() is + // being called but GCC only gave us an implementation for + // Foo::~Foo(int32). See computeCallgraph.js for a little more info. + var name = entry.name; + if (name.indexOf("::~") > 0 && name.indexOf("()") > 0) { + var callee = name.replace("()", "(int32)"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + // Similarly, a call to a C1 constructor might invoke the C4 constructor. A + // mangled constructor will be something like _ZN<length><name>C1E... or in + // the case of a templatized constructor, _ZN<length><name>C1I...EE... so + // we hack it and look for "C1E" or "C1I" and replace them with their C4 + // variants. This will have rare false matches, but so far we haven't hit + // any external function calls of that sort. + if (entry.mangledName().includes("C1E") || entry.mangledName().includes("C1I")) { + var callee = name.replace("C1E", "C4E").replace("C1I", "C4I"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + // Hack to manually follow some typedefs that show up on some functions. + // This is a bug in the sixgill GCC plugin I think, since sixgill is + // supposed to follow any typedefs itself. + if (/mozilla::dom::Element/.test(name)) { + var callee = name.replace("mozilla::dom::Element", "Document::Element"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + // Hack for contravariant return types. When overriding a virtual method + // with a method that returns a different return type (a subtype of the + // original return type), we are getting the right mangled name but the + // wrong return type in the unmangled name. + if (/\$nsTextFrame*/.test(name)) { + var callee = name.replace("nsTextFrame", "nsIFrame"); + addCallee(new CallSite(name, entry.safeArguments, entry.stack[0].location, entry.parameterNames)); + return true; + } + + return false; +} + +function processRoot(name) +{ + var safeArguments = []; + var parameterNames = {}; + var worklist = [new WorklistEntry(name, safeArguments, [new CallSite(name, safeArguments, null, parameterNames)], parameterNames)]; + + reachable = {}; + + while (worklist.length > 0) { + var entry = worklist.pop(); + + // In principle we would be better off doing a meet-over-paths here to get + // the common subset of arguments which are safe to write through. However, + // analyzing functions separately for each subset if simpler, ensures that + // the stack traces we produce accurately characterize the stack arguments, + // and should be fast enough for now. + + if (entry.mangledName() in reachable) + continue; + reachable[entry.mangledName()] = true; + + if (ignoreContents(entry)) + continue; + + var data = xdb.read_entry(entry.name); + var dataString = data.readString(); + var callees = []; + if (dataString.length) { + // Reverse the order of the bodies we process so that we visit the + // outer function and see its assignments before the inner loops. + assignments = {}; + reachableLoops = {}; + var bodies = JSON.parse(dataString).reverse(); + for (var body of bodies) { + if (!body.BlockId.Loop || body.BlockId.Loop in reachableLoops) { + currentBody = body; + process(entry, body, Array.prototype.push.bind(callees)); + } + } + } else { + if (!maybeProcessMissingFunction(entry, Array.prototype.push.bind(callees))) + checkExternalFunction(entry); + } + xdb.free_string(data); + + for (var callee of callees) { + if (!ignoreCallEdge(entry, callee.callee)) { + var nstack = [callee, ...entry.stack]; + worklist.push(new WorklistEntry(callee.callee, callee.safeArguments, nstack, callee.parameterNames)); + } + } + } +} + +function isEdgeSafeArgument(entry, exp) +{ + var fields; + [exp, fields] = stripFields(exp); + + if (exp.Kind == "Var" && isLocalVariable(exp.Variable)) + return true; + if (exp.Kind == "Drf" && exp.Exp[0].Kind == "Var") { + var variable = exp.Exp[0].Variable; + return isSafeVariable(entry, variable); + } + if (isZero(exp)) + return true; + return false; +} + +function getEdgeSafeArguments(entry, edge, callee) +{ + assert(edge.Kind == "Call"); + var res = []; + if ("PEdgeCallInstance" in edge) { + if (isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + res.push(0); + } + if ("PEdgeCallArguments" in edge) { + var args = edge.PEdgeCallArguments.Exp; + for (var i = 0; i < args.length; i++) { + if (isEdgeSafeArgument(entry, args[i])) + res.push(i + 1); + } + } + return res; +} + +function singleAssignment(name) +{ + if (name in assignments) { + var edges = assignments[name]; + if (edges.length == 1) + return edges[0]; + } + return null; +} + +function expressionValueEdge(exp) { + if (!(exp.Kind == "Var" && exp.Variable.Kind == "Temp")) + return null; + const assign = singleAssignment(variableName(exp.Variable)); + if (!assign) + return null; + const [body, edge] = assign; + return edge; +} + +// Examples: +// +// void foo(type* aSafe) { +// type* safeBecauseNew = new type(...); +// type* unsafeBecauseMultipleAssignments = new type(...); +// if (rand()) +// unsafeBecauseMultipleAssignments = bar(); +// type* safeBecauseSingleAssignmentOfSafe = aSafe; +// } +// +function isSafeVariable(entry, variable) +{ + var index = safeArgumentIndex(variable); + if (index >= 0) + return entry.isSafeArgument(index); + + if (variable.Kind != "Temp" && variable.Kind != "Local") + return false; + var name = variableName(variable); + + if (!entry.safeLocals) + entry.safeLocals = new Map; + if (entry.safeLocals.has(name)) + return entry.safeLocals.get(name); + + const safe = isSafeLocalVariable(entry, name); + entry.safeLocals.set(name, safe); + return safe; +} + +function isSafeLocalVariable(entry, name) +{ + // If there is a single place where this variable has been assigned on + // edges we are considering, look at that edge. + var assign = singleAssignment(name); + if (assign) { + const [body, edge] = assign; + + // Treat temporary pointers to DebugOnly contents as thread local. + if (isDirectCall(edge, /DebugOnly.*?::operator/)) + return true; + + // Treat heap allocated pointers as thread local during construction. + // Hopefully the construction code doesn't leak pointers to the object + // to places where other threads might access it. + if (isDirectCall(edge, /operator new/) || + isDirectCall(edge, /nsCSSValue::Array::Create/)) + { + return true; + } + + if ("PEdgeCallInstance" in edge) { + // References to the contents of an array are threadsafe if the array + // itself is threadsafe. + if ((isDirectCall(edge, /operator\[\]/) || + isDirectCall(edge, /nsTArray.*?::InsertElementAt\b/) || + isDirectCall(edge, /nsStyleContent::ContentAt/) || + isDirectCall(edge, /nsTArray_base.*?::GetAutoArrayBuffer\b/)) && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + { + return true; + } + + // Watch for the coerced result of a getter_AddRefs or getter_Copies call. + if (isDirectCall(edge, /operator /)) { + var otherEdge = expressionValueEdge(edge.PEdgeCallInstance.Exp); + if (otherEdge && + isDirectCall(otherEdge, /getter_(?:AddRefs|Copies)/) && + isEdgeSafeArgument(entry, otherEdge.PEdgeCallArguments.Exp[0])) + { + return true; + } + } + + // RefPtr::operator->() and operator* transmit the safety of the + // RefPtr to the return value. + if (isDirectCall(edge, /RefPtr<.*?>::operator(->|\*)\(\)/) && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + { + return true; + } + + // Placement-new returns a pointer that is as safe as the pointer + // passed to it. Exp[0] is the size, Exp[1] is the pointer/address. + // Note that the invocation of the constructor is a separate call, + // and so need not be considered here. + if (isDirectCall(edge, /operator new/) && + edge.PEdgeCallInstance.Exp.length == 2 && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp[1])) + { + return true; + } + + // Coercion via AsAString preserves safety. + if (isDirectCall(edge, /AsAString/) && + isEdgeSafeArgument(entry, edge.PEdgeCallInstance.Exp)) + { + return true; + } + + // Special case: + // + // keyframe->mTimingFunction.emplace() + // keyframe->mTimingFunction->Init() + // + // The object calling Init should be considered safe here because + // we just emplaced it, though in general keyframe::operator-> + // could do something crazy. + if (isDirectCall(edge, /operator->/)) do { + const predges = getPredecessors(body)[edge.Index[0]]; + if (!predges || predges.length != 1) + break; + const predge = predges[0]; + if (!isDirectCall(predge, /\bemplace\b/)) + break; + const instance = predge.PEdgeCallInstance; + if (JSON.stringify(instance) == JSON.stringify(edge.PEdgeCallInstance)) + return true; + } while (false); + } + + if (isSafeAssignment(entry, edge, name)) + return true; + + // Watch out for variables which were assigned arguments. + var rhsVariable = variableAssignRhs(edge); + if (rhsVariable) + return isSafeVariable(entry, rhsVariable); + } + + // When temporary stack structures are created (either to return or to call + // methods on without assigning them a name), the generated sixgill JSON is + // rather strange. The temporary has structure type and is never assigned + // to, but is dereferenced. GCC is probably not showing us everything it is + // doing to compile this code. Pattern match for this case here. + + // The variable should have structure type. + var type = null; + for (var defvar of currentBody.DefineVariable) { + if (variableName(defvar.Variable) == name) { + type = defvar.Type; + break; + } + } + if (!type || type.Kind != "CSU") + return false; + + // The variable should not have been written to anywhere up to this point. + // If it is initialized at this point we should have seen *some* write + // already, since the CFG edges are visited in reverse post order. + if (name in assignments) + return false; + + return true; +} + +function isSafeMemberPointer(containerType, memberName, memberType) +{ + // nsTArray owns its header. + if (containerType.includes("nsTArray_base") && memberName == "mHdr") + return true; + + if (memberType.Kind != 'Pointer') + return false; + + // Special-cases go here :) + return false; +} + +// Return whether 'exp == value' holds only when execution is on the main thread. +function testFailsOffMainThread(exp, value) { + switch (exp.Kind) { + case "Drf": + var edge = expressionValueEdge(exp.Exp[0]); + if (edge) { + if (isDirectCall(edge, /NS_IsMainThread/) && value) + return true; + if (isDirectCall(edge, /IsInServoTraversal/) && !value) + return true; + if (isDirectCall(edge, /IsCurrentThreadInServoTraversal/) && !value) + return true; + if (isDirectCall(edge, /__builtin_expect/)) + return testFailsOffMainThread(edge.PEdgeCallArguments.Exp[0], value); + if (edge.Kind == "Assign") + return testFailsOffMainThread(edge.Exp[1], value); + } + break; + case "Unop": + if (exp.OpCode == "LogicalNot") + return testFailsOffMainThread(exp.Exp[0], !value); + break; + case "Binop": + if (exp.OpCode == "NotEqual" || exp.OpCode == "Equal") { + var cmpExp = isZero(exp.Exp[0]) + ? exp.Exp[1] + : (isZero(exp.Exp[1]) ? exp.Exp[0] : null); + if (cmpExp) + return testFailsOffMainThread(cmpExp, exp.OpCode == "NotEqual" ? value : !value); + } + break; + case "Int": + if (exp.String == "0" && value) + return true; + if (exp.String == "1" && !value) + return true; + break; + } + return false; +} |