Source code
Revision control
Copy as Markdown
Other Tools
/* 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
#include "CollectorLogAnalyzer.h"
#include <cinttypes>
#include <queue>
#include "CollectorLogAnalyzerBackground.h"
#include "mozilla/ErrorResult.h"
#include "mozilla/HashTable.h"
#include "mozilla/SIMD.h"
#include "mozilla/Vector.h"
#include "mozilla/dom/ChromeUtils.h"
#include "mozilla/dom/FileCreatorHelper.h"
#include "mozilla/dom/Promise.h"
#include "nsFileStreams.h"
#include "nsIFile.h"
#include "nsIGlobalObject.h"
#include "nsXULAppAPI.h"
#include "prio.h"
namespace mozilla {
static constexpr auto MAX_QUERY_RESULTS =
dom::CollectorLogAnalyzer_Binding::MAX_QUERY_RESULTS;
static constexpr auto SAMPLE_COUNT =
dom::CollectorLogAnalyzer_Binding::SAMPLE_COUNT;
NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE(CollectorLogAnalyzer, mGlobal)
NS_IMPL_CYCLE_COLLECTING_ADDREF(CollectorLogAnalyzer)
NS_IMPL_CYCLE_COLLECTING_RELEASE(CollectorLogAnalyzer)
NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(CollectorLogAnalyzer)
NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY
NS_INTERFACE_MAP_ENTRY(nsISupports)
NS_INTERFACE_MAP_END
CollectorLogAnalyzer::CollectorLogAnalyzer(nsIGlobalObject* aGlobal,
const nsAString& aCCLogPath,
const nsAString& aGCLogPath)
: mGlobal(aGlobal), mCCLogPath(aCCLogPath), mGCLogPath(aGCLogPath) {
MOZ_ALWAYS_SUCCEEDS(
NS_CreateBackgroundTaskQueue("CollectorLogAnalyzer::BackgroundTaskQueue",
getter_AddRefs(mBackgroundEventTarget)));
MOZ_RELEASE_ASSERT(mBackgroundEventTarget);
mBackground = MakeRefPtr<CollectorLogAnalyzerBackground>();
}
JSObject* CollectorLogAnalyzer::WrapObject(JSContext* aCx,
JS::Handle<JSObject*> aGivenProto) {
return dom::CollectorLogAnalyzer_Binding::Wrap(aCx, this, aGivenProto);
}
template <typename T>
static void ResolveJSPromise(dom::Promise* aPromise, T&& aValue) {
if constexpr (std::is_same_v<T, Ok>) {
aPromise->MaybeResolveWithUndefined();
} else {
aPromise->MaybeResolve(std::forward<T>(aValue));
}
}
static nsCString FormatErrorMessage(nsresult aError,
const nsCString& aMessage) {
nsAutoCString errorName;
GetErrorName(aError, errorName);
nsCString msg(aMessage);
msg.AppendPrintf(" (%s)", errorName.get());
return msg;
}
static void RejectJSPromise(dom::Promise* aPromise, const LogError& aError) {
const auto errMsg = FormatErrorMessage(aError.Code(), aError.Message());
aPromise->MaybeRejectWithUnknownError(errMsg);
}
template <typename OkT, typename Fn>
already_AddRefed<dom::Promise> CollectorLogAnalyzer::DispatchToBackground(
ErrorResult& aError, Fn aFunc) {
MOZ_RELEASE_ASSERT(XRE_IsParentProcess());
MOZ_RELEASE_ASSERT(mBackgroundEventTarget);
RefPtr<dom::Promise> jsPromise = dom::Promise::Create(mGlobal, aError);
if (aError.Failed()) {
return nullptr;
}
MOZ_ASSERT(jsPromise);
auto nativePromise =
MakeRefPtr<typename MozPromise<OkT, LogError, true>::Private>(__func__);
mBackgroundEventTarget->Dispatch(
NS_NewRunnableFunction(
"CollectorLogAnalyzer::BackgroundTaskQueue::Dispatch",
[nativePromise, func = std::move(aFunc)] {
Result<OkT, LogError> result = func();
if (result.isErr()) {
nativePromise->Reject(result.unwrapErr(), __func__);
} else {
nativePromise->Resolve(result.unwrap(), __func__);
}
}),
NS_DISPATCH_EVENT_MAY_BLOCK);
nativePromise->Then(
GetCurrentSerialEventTarget(), __func__,
[promise = RefPtr(jsPromise)](OkT&& ok) {
ResolveJSPromise(promise, std::forward<OkT>(ok));
},
[promise = RefPtr(jsPromise)](const LogError& err) {
RejectJSPromise(promise, err);
});
return jsPromise.forget();
}
enum class GCThingKind {
None,
Marked,
Unmarked,
};
Result<Ok, LogError> CollectorLogAnalyzerBackground::EnsureInitialized() {
if (!mInitialized) {
return Err(LogError(NS_ERROR_NOT_INITIALIZED,
"The CollectorLogAnalyzer is not initialized"));
}
return Ok();
}
template <typename TMap, typename TKey, typename TValue>
Result<Ok, LogError> PutInMap(TMap& aMap, TKey&& aKey, TValue&& aValue) {
if (!aMap.put(std::forward<TKey>(aKey), std::forward<TValue>(aValue))) {
return Err(
LogError(NS_ERROR_OUT_OF_MEMORY, "Out of memory growing hash map"));
}
return Ok();
}
template <typename TMap, typename TKey, typename TValue>
Result<Ok, LogError> AddToMap(TMap& aMap, typename TMap::AddPtr& aAddPtr,
TKey&& aKey, TValue&& aValue) {
if (!aMap.add(aAddPtr, std::forward<TKey>(aKey),
std::forward<TValue>(aValue))) {
return Err(
LogError(NS_ERROR_OUT_OF_MEMORY, "Out of memory growing hash map"));
}
return Ok();
}
template <typename TSet, typename TValue>
Result<Ok, LogError> PutInSet(TSet& set, TValue&& aValue) {
if (!set.put(std::forward<TValue>(aValue))) {
return Err(
LogError(NS_ERROR_OUT_OF_MEMORY, "Out of memory growing hash set"));
}
return Ok();
}
template <typename TVector, typename TValue>
Result<Ok, LogError> AppendToVector(TVector& vec, TValue&& aValue) {
if (!vec.append(std::forward<TValue>(aValue))) {
return Err(LogError(NS_ERROR_OUT_OF_MEMORY,
"Out of memory growing vector. Length: %zu",
vec.length()));
}
return Ok();
}
[[nodiscard]] static bool SkipCommentLine(const nsACString& aBuf,
size_t* aCurrChar) {
if (aBuf[*aCurrChar] != '#') {
return false;
}
const char* start = aBuf.BeginReading();
const char* newline =
SIMD::memchr8(start + *aCurrChar, '\n', aBuf.Length() - *aCurrChar);
if (!newline) {
return false;
}
*aCurrChar = newline - start + 1;
return true;
}
[[nodiscard]] static bool MatchLiteral(const nsACString& aBuf,
size_t* aCurrChar,
const nsLiteralCString& aLiteral) {
size_t currChar = *aCurrChar;
if (aLiteral.Length() >= aBuf.Length() - currChar) {
return false;
}
if (memcmp(aBuf.BeginReading() + currChar, aLiteral.get(),
aLiteral.Length()) != 0) {
return false;
}
*aCurrChar += aLiteral.Length();
return true;
}
[[nodiscard]] static bool ParsePointer(const nsACString& aBuf,
size_t* aCurrChar, uint64_t* aPtr) {
size_t currChar = *aCurrChar;
if (MatchLiteral(aBuf, &currChar, "(nil)"_ns)) {
*aPtr = 0;
*aCurrChar = currChar;
return true;
}
char* end = nullptr;
const char* begin = aBuf.BeginReading() + currChar;
*aPtr = strtoull(begin, &end, 16);
if (end == begin) {
return false;
}
*aCurrChar = currChar + (end - begin);
return true;
}
[[nodiscard]] static bool ParseDecimal(const nsACString& aBuf,
size_t* aCurrChar, int32_t* aValue) {
size_t currChar = *aCurrChar;
char* end = nullptr;
const char* begin = aBuf.BeginReading() + currChar;
*aValue = strtol(begin, &end, 10);
if (end == begin) {
return false;
}
*aCurrChar = currChar + (end - begin);
return true;
}
static void SkipTabsAndSpaces(const nsACString& aBuf, size_t* aCurrChar) {
size_t currChar = *aCurrChar;
while (currChar < aBuf.Length() &&
(aBuf[currChar] == ' ' || aBuf[currChar] == '\t')) {
currChar++;
}
*aCurrChar = currChar;
}
[[nodiscard]] static bool MatchLineEnd(const nsACString& aBuf,
size_t* aCurrChar) {
size_t currChar = *aCurrChar;
if (currChar < aBuf.Length() && aBuf[currChar] == '\r') {
currChar++;
}
if (currChar >= aBuf.Length() || aBuf[currChar] != '\n') {
return false;
}
currChar++;
*aCurrChar = currChar;
return true;
}
// If we have a newline character after the current character in the
// buffer, this will collect the contents of the buffer starting at
// *aCurrChar up until the first newline.
[[nodiscard]] static bool MatchRemainingLine(const nsACString& aBuf,
size_t* aCurrChar,
nsACString* aResult) {
size_t currChar = *aCurrChar;
size_t resultStart = currChar;
while (currChar < aBuf.Length() && aBuf[currChar] != '\r' &&
aBuf[currChar] != '\n') {
currChar++;
}
size_t resultEnd = currChar;
if (!MatchLineEnd(aBuf, &currChar)) {
return false;
}
aResult->Assign(Substring(aBuf, resultStart, resultEnd - resultStart));
*aCurrChar = currChar;
return true;
}
[[nodiscard]] static bool MatchEndSection(const nsACString& aBuf,
size_t* aCurrChar) {
size_t currChar = *aCurrChar;
if (!MatchLiteral(aBuf, &currChar, "=========="_ns)) {
return false;
}
if (!MatchLineEnd(aBuf, &currChar)) {
return false;
}
*aCurrChar = currChar;
return true;
}
[[nodiscard]] static bool ParseCCNode(const nsACString& aBuf, size_t* aCurrChar,
uint64_t* aPtr, int32_t* aRefCnt,
GCThingKind* aGCKind,
nsACString* aLabel) {
size_t currChar = *aCurrChar;
if (!ParsePointer(aBuf, &currChar, aPtr)) {
return false;
}
if (MatchLiteral(aBuf, &currChar, " [gc"_ns)) {
*aRefCnt = -1;
if (MatchLiteral(aBuf, &currChar, ".marked]"_ns)) {
*aGCKind = GCThingKind::Marked;
} else if (MatchLiteral(aBuf, &currChar, "]"_ns)) {
*aGCKind = GCThingKind::Unmarked;
} else {
return false;
}
} else if (MatchLiteral(aBuf, &currChar, " [rc="_ns)) {
*aGCKind = GCThingKind::None;
if (!ParseDecimal(aBuf, &currChar, aRefCnt)) {
return false;
}
if (!MatchLiteral(aBuf, &currChar, "]"_ns)) {
return false;
}
} else {
return false;
}
SkipTabsAndSpaces(aBuf, &currChar);
if (!MatchRemainingLine(aBuf, &currChar, aLabel)) {
return false;
}
*aCurrChar = currChar;
return true;
}
enum class GCColor {
Black,
Gray,
White,
};
[[nodiscard]] static bool ParseGCNode(const nsACString& aBuf, size_t* aCurrChar,
uint64_t* aPtr, GCColor* aColor,
nsACString* aLabel) {
size_t currChar = *aCurrChar;
if (!ParsePointer(aBuf, &currChar, aPtr)) {
return false;
}
if (MatchLiteral(aBuf, &currChar, " B"_ns)) {
*aColor = GCColor::Black;
} else if (MatchLiteral(aBuf, &currChar, " G"_ns)) {
*aColor = GCColor::Gray;
} else if (MatchLiteral(aBuf, &currChar, " W"_ns)) {
*aColor = GCColor::White;
} else {
return false;
}
SkipTabsAndSpaces(aBuf, &currChar);
if (!MatchRemainingLine(aBuf, &currChar, aLabel)) {
return false;
}
*aCurrChar = currChar;
return true;
}
[[nodiscard]] static bool ParseCCEdge(const nsACString& aBuf, size_t* aCurrChar,
uint64_t* aPtr, int32_t* aNesting,
bool* aWeak, nsACString* aLabel) {
size_t currChar = *aCurrChar;
if (!MatchLiteral(aBuf, &currChar, "> "_ns)) {
return false;
}
if (!ParsePointer(aBuf, &currChar, aPtr)) {
return false;
}
if (MatchLiteral(aBuf, &currChar, " [weak]"_ns)) {
*aWeak = true;
}
if (MatchLiteral(aBuf, &currChar, " [nesting="_ns)) {
if (!ParseDecimal(aBuf, &currChar, aNesting)) {
return false;
}
if (!MatchLiteral(aBuf, &currChar, "]"_ns)) {
return false;
}
}
SkipTabsAndSpaces(aBuf, &currChar);
if (!MatchRemainingLine(aBuf, &currChar, aLabel)) {
return false;
}
*aCurrChar = currChar;
return true;
}
[[nodiscard]] static bool ParseGCEdge(const nsACString& aBuf, size_t* aCurrChar,
uint64_t* aPtr, bool* aWeak,
nsACString* aLabel) {
size_t currChar = *aCurrChar;
if (!MatchLiteral(aBuf, &currChar, "> "_ns)) {
return false;
}
if (!ParsePointer(aBuf, &currChar, aPtr)) {
return false;
}
if (!MatchLiteral(aBuf, &currChar, " B"_ns) &&
!MatchLiteral(aBuf, &currChar, " G"_ns) &&
!MatchLiteral(aBuf, &currChar, " W"_ns)) {
return false;
}
if (MatchLiteral(aBuf, &currChar, " [weak]"_ns)) {
*aWeak = true;
}
SkipTabsAndSpaces(aBuf, &currChar);
if (!MatchRemainingLine(aBuf, &currChar, aLabel)) {
return false;
}
*aCurrChar = currChar;
return true;
}
[[nodiscard]] static bool ParseIncrementalRoot(const nsACString& aBuf,
size_t* aCurrChar,
uint64_t* aPtr) {
size_t currChar = *aCurrChar;
if (!MatchLiteral(aBuf, &currChar, "IncrementalRoot "_ns)) {
return false;
}
if (!ParsePointer(aBuf, &currChar, aPtr)) {
return false;
}
if (!MatchLineEnd(aBuf, &currChar)) {
return false;
}
*aCurrChar = currChar;
return true;
}
[[nodiscard]] static bool ParseWeakMapEntry(const nsACString& aBuf,
size_t* aCurrChar,
WeakMapEntry* aEntry) {
size_t currChar = *aCurrChar;
if (!MatchLiteral(aBuf, &currChar, "WeakMapEntry map="_ns)) {
return false;
}
if (!ParsePointer(aBuf, &currChar, &aEntry->mMap)) {
return false;
}
if (!MatchLiteral(aBuf, &currChar, " key="_ns)) {
return false;
}
if (!ParsePointer(aBuf, &currChar, &aEntry->mKey)) {
return false;
}
if (!MatchLiteral(aBuf, &currChar, " keyDelegate="_ns)) {
return false;
}
if (!ParsePointer(aBuf, &currChar, &aEntry->mKeyDelegate)) {
return false;
}
if (!MatchLiteral(aBuf, &currChar, " value="_ns)) {
return false;
}
if (!ParsePointer(aBuf, &currChar, &aEntry->mValue)) {
return false;
}
if (!MatchLineEnd(aBuf, &currChar)) {
return false;
}
*aCurrChar = currChar;
return true;
}
[[nodiscard]] static bool ParseResult(const nsACString& aBuf, size_t* aCurrChar,
uint64_t* aPtr, int32_t* aKnown) {
size_t currChar = *aCurrChar;
if (!ParsePointer(aBuf, &currChar, aPtr)) {
return false;
}
if (MatchLiteral(aBuf, &currChar, " [garbage]"_ns)) {
*aKnown = -1;
} else if (MatchLiteral(aBuf, &currChar, " [known="_ns)) {
if (!ParseDecimal(aBuf, &currChar, aKnown)) {
return false;
}
if (!MatchLiteral(aBuf, &currChar, "]"_ns)) {
return false;
}
} else {
return false;
}
if (!MatchLineEnd(aBuf, &currChar)) {
return false;
}
*aCurrChar = currChar;
return true;
}
// Find and return the index of aNeedle within aHaystack. If aNeedle can't be
// found, this returns -1
static int64_t FindMatch(mozilla::Span<const char> aHaystack,
const nsCString& aNeedle) {
MOZ_ASSERT(aNeedle.Length() > 0);
if (aNeedle.Length() == 1) {
const char* pos =
SIMD::memchr8(aHaystack.Elements(), aNeedle[0], aHaystack.Length());
if (pos) {
return pos - aHaystack.Elements();
}
return -1;
}
size_t index = 0;
while (aHaystack.Length() >= aNeedle.Length()) {
const char* pos;
const size_t inlineLookaheadChars = 2;
size_t searchLen =
aHaystack.Length() - aNeedle.Length() + inlineLookaheadChars;
pos = SIMD::memchr2x8(aHaystack.Elements(), aNeedle[0], aNeedle[1],
searchLen);
if (!pos) {
return -1;
}
size_t localIndex = pos - aHaystack.Elements();
aHaystack = aHaystack.Subspan(localIndex);
index += localIndex;
if (memcmp(aNeedle.get() + inlineLookaheadChars,
aHaystack.Elements() + inlineLookaheadChars,
aNeedle.Length() - inlineLookaheadChars) == 0) {
return int64_t(index);
}
aHaystack = aHaystack.Subspan(1);
index += 1;
}
return -1;
}
// Since we store all the strings in one contiguous buffer for search purposes
// (i.e., aHaystack), we expose this helper to get the boundaries of a string
// based on the start index (aInnerIndex) of a substring within it. We return
// the start and end index of the string in aStart and aEnd respectively. The
// boundaries of a string are determined either by the presence of a null
// character or the limits of the buffer.
static void GetStringBoundaries(mozilla::Span<const char> aHaystack,
size_t aInnerIndex, size_t* aStart,
size_t* aEnd) {
MOZ_ASSERT(aInnerIndex < aHaystack.Length());
MOZ_ASSERT(aHaystack[aInnerIndex] != '\0');
MOZ_ASSERT(uint64_t(aHaystack.Length()) <=
uint64_t(std::numeric_limits<int64_t>::max()));
*aStart = 0;
for (int64_t i = int64_t(aInnerIndex) - 1; i >= 0; --i) {
if (aHaystack[i] == '\0') {
*aStart = i + 1;
break;
}
}
const char* endPtr = SIMD::memchr8(aHaystack.Elements() + aInnerIndex, '\0',
aHaystack.Length() - aInnerIndex);
if (endPtr == nullptr) {
*aEnd = aHaystack.Length();
} else {
*aEnd = endPtr - aHaystack.Elements();
}
}
// This finds every occurrence of aQuery in a contiguous buffer of strings
// delimited by null characters. For example, if aQuery is "Global", then in a
// typical log's processed string buffer this should find the index of
// "nsGlobalWindowInner" and the index of "nsGlobalWindowOuter", among others.
static Result<HashSet<size_t>, LogError> FindStringIndices(
const Vector<char>& aStrings, const nsCString& aQuery) {
HashSet<size_t> result;
mozilla::Span<const char> haystack = aStrings;
size_t offset = 0;
int64_t match = -1;
while (offset < haystack.Length() &&
(match = FindMatch(haystack.subspan(offset), aQuery)) != -1) {
size_t start;
size_t end;
GetStringBoundaries(haystack, match + offset, &start, &end);
MOZ_TRY(PutInSet(result, start));
offset = end;
}
return result;
}
// There are typically a lot of duplicated strings within a GC/CC log, so we
// intern strings into one contiguous buffer and represent node/edge labels
// as indexes into this buffer. If two nodes have the same label, they will
// have the same index. This function takes aStr and returns the index at
// which the string can be found in the contiguous buffer (mStrings). If aStr
// does not already exist within mStrings, this will add it.
Result<StringBufferIndex, LogError>
CollectorLogAnalyzerBackground::InternString(const nsCString& aStr) {
auto p = mStringTable.lookupForAdd(aStr);
if (!p) {
size_t res = mStrings.length();
size_t reserveLength = aStr.Length() + 1;
if (!mStrings.growByUninitialized(reserveLength)) {
return Err(LogError(NS_ERROR_OUT_OF_MEMORY,
"Out of memory growing string buffer"));
}
char* writePtr = mStrings.end() - reserveLength;
memcpy(writePtr, aStr.get(), aStr.Length());
writePtr[reserveLength - 1] = '\0';
MOZ_TRY(AddToMap(mStringTable, p, aStr, res));
}
return p->value();
}
Result<NodeTableIndex, LogError> CollectorLogAnalyzerBackground::EnsureNode(
NodeId aNodeId) {
auto p = mNodeIdsToIndices.lookupForAdd(aNodeId);
if (!p) {
NodeTableIndex index = mNodeIds.length();
MOZ_TRY(AppendToVector(mNodeIds, aNodeId));
MOZ_TRY(AddToMap(mNodeIdsToIndices, p, aNodeId, index));
MOZ_TRY(AppendToVector(mNodeLabels, INVALID_STRING));
MOZ_TRY(AppendToVector(mNodeFlags, 0));
MOZ_TRY(AppendToVector(mObservedReferenceCounts, 0));
NodeEdgesDescriptor edges = {};
edges.mCC = INVALID_NODE;
edges.mGC = INVALID_NODE;
edges.mWeakMap = INVALID_NODE;
MOZ_TRY(AppendToVector(mNodeEdges, edges));
}
return p->value();
}
Result<Ok, LogError> CollectorLogAnalyzerBackground::AddWeakMapEdge(
NodeTableIndex aKey, NodeTableIndex aMap, NodeTableIndex aValue,
bool aKeyDelegate, bool aKeyIsSource) {
WeakMapEdge edge = {};
edge.mKey = aKey;
edge.mMap = aMap;
edge.mValue = aValue;
if (aKeyDelegate) {
edge.mKind = WeakMapEdgeKind::WeakMapKeyDelegate;
} else {
edge.mKind = WeakMapEdgeKind::WeakMapKey;
}
edge.mKeyIsSource = aKeyIsSource;
MOZ_TRY(AppendToVector(mWeakMapEdges, edge));
mNodeEdges[edge.source()].mWeakMapCount++;
return Ok();
}
Result<Ok, LogError> CollectorLogAnalyzerBackground::AddWeakMapEntry(
const WeakMapEntry& aEntry) {
NodeTableIndex keyIndex = MOZ_TRY(EnsureNode(aEntry.mKey));
NodeTableIndex mapIndex = MOZ_TRY(EnsureNode(aEntry.mMap));
NodeTableIndex valueIndex = MOZ_TRY(EnsureNode(aEntry.mValue));
MOZ_TRY(AddWeakMapEdge(keyIndex, mapIndex, valueIndex,
/* aKeyDelegate = */ false,
/* aKeyIsSource = */ true));
MOZ_TRY(AddWeakMapEdge(keyIndex, mapIndex, valueIndex,
/* aKeyDelegate = */ false,
/* aKeyIsSource = */ false));
if (aEntry.mKeyDelegate != 0) {
NodeTableIndex keyDelegateIndex = MOZ_TRY(EnsureNode(aEntry.mKeyDelegate));
MOZ_TRY(AddWeakMapEdge(keyDelegateIndex, mapIndex, keyIndex,
/* aKeyDelegate = */ true,
/* aKeyIsSource = */ true));
MOZ_TRY(AddWeakMapEdge(keyDelegateIndex, mapIndex, keyIndex,
/* aKeyDelegate = */ true,
/* aKeyIsSource = */ false));
}
return Ok();
}
Result<Ok, LogError> CollectorLogAnalyzerBackground::AddCCEdge(
NodeTableIndex aCurrentNode, NodeTableIndex aEdge,
StringBufferIndex aLabel) {
NodeEdgesDescriptor& edges = mNodeEdges[aCurrentNode];
MOZ_ASSERT(edges.mCC + edges.mCCCount == mEdges.length());
MOZ_TRY(AppendToVector(mEdges, aEdge));
MOZ_TRY(AppendToVector(mEdgeLabels, aLabel));
edges.mCCCount++;
return Ok();
}
Result<Ok, LogError> CollectorLogAnalyzerBackground::AddGCEdge(
NodeTableIndex aCurrentNode, NodeTableIndex aEdge,
StringBufferIndex aLabel) {
NodeEdgesDescriptor& edges = mNodeEdges[aCurrentNode];
MOZ_ASSERT(edges.mGC + edges.mGCCount == mEdges.length());
MOZ_TRY(AppendToVector(mEdges, aEdge));
MOZ_TRY(AppendToVector(mEdgeLabels, aLabel));
edges.mGCCount++;
return Ok();
}
Result<size_t, LogError>
CollectorLogAnalyzerBackground::IngestCycleCollectorLog(const nsACString& aBuf,
bool aContainsFileEnd) {
size_t currChar = 0;
size_t prevChar = 0;
while (currChar < aBuf.Length()) {
mCCFileProgress += currChar - prevChar;
prevChar = currChar;
mCCLineNumber++;
if (SkipCommentLine(aBuf, &currChar)) {
continue;
}
if (mCurrentCCSection == CCLogSection::Graph) {
if (MatchEndSection(aBuf, &currChar)) {
mCurrentCCSection = CCLogSection::Results;
continue;
}
uint64_t ptr;
int32_t refCount; // -1 if does not exist
GCThingKind gcKind;
nsAutoCString label;
if (ParseCCNode(aBuf, &currChar, &ptr, &refCount, &gcKind, &label)) {
mCurrentCCNode = MOZ_TRY(EnsureNode(ptr));
StringBufferIndex labelIndex = MOZ_TRY(InternString(label));
mNodeLabels[mCurrentCCNode] = labelIndex;
if (gcKind == GCThingKind::None) {
mNodeFlags[mCurrentCCNode] |=
dom::CollectorNodeFlags_Binding::CC_MANAGED;
if (refCount < 0) {
return Err(
LogError(NS_ERROR_FILE_CORRUPTED,
"Encountered a negative refcount in the CC log"));
}
MOZ_TRY(
PutInMap(mCCReferenceCounts, mCurrentCCNode, uint32_t(refCount)));
} else if (!mHaveGC) {
mNodeFlags[mCurrentCCNode] |=
dom::CollectorNodeFlags_Binding::GC_MARKED;
if (gcKind == GCThingKind::Unmarked) {
mNodeFlags[mCurrentCCNode] |=
dom::CollectorNodeFlags_Binding::GC_GRAY;
}
}
if (mNodeEdges[mCurrentCCNode].mCC != INVALID_NODE) {
return Err(LogError(
NS_ERROR_FILE_CORRUPTED,
"Encountered node 0x%" PRIx64 " twice in the CC log", ptr));
}
mNodeEdges[mCurrentCCNode].mCC = mEdges.length();
continue;
}
int32_t nesting = 0;
bool weak = false;
if (ParseCCEdge(aBuf, &currChar, &ptr, &nesting, &weak, &label)) {
if (mCurrentCCNode >= mNodeEdges.length()) {
return Err(
LogError(NS_ERROR_FILE_CORRUPTED,
"Invalid log format: edge encountered before a node"));
}
if (mHaveGC && nesting != 0) {
continue;
}
if (weak) {
continue;
}
StringBufferIndex labelIndex = MOZ_TRY(InternString(label));
NodeTableIndex edge = MOZ_TRY(EnsureNode(ptr));
MOZ_TRY(AddCCEdge(mCurrentCCNode, edge, labelIndex));
continue;
}
if (ParseIncrementalRoot(aBuf, &currChar, &ptr)) {
NodeTableIndex node = MOZ_TRY(EnsureNode(ptr));
mNodeFlags[node] |= dom::CollectorNodeFlags_Binding::INCREMENTAL_ROOT;
MOZ_TRY(AppendToVector(mIncrementalRoots, node));
continue;
}
WeakMapEntry entry = {};
if (ParseWeakMapEntry(aBuf, &currChar, &entry)) {
MOZ_TRY(AddWeakMapEntry(entry));
continue;
}
} else if (mCurrentCCSection == CCLogSection::Results) {
uint64_t ptr;
int32_t known;
if (ParseResult(aBuf, &currChar, &ptr, &known)) {
NodeTableIndex node = MOZ_TRY(EnsureNode(ptr));
mNodeFlags[node] |= dom::CollectorNodeFlags_Binding::CC_MANAGED;
if (known == -1) {
mNodeFlags[node] |= dom::CollectorNodeFlags_Binding::GARBAGE;
} else {
mNodeFlags[node] |= dom::CollectorNodeFlags_Binding::ROOT;
}
continue;
}
} else {
MOZ_CRASH("Unexpected section");
}
nsAutoCString line;
bool matchedLine = MatchRemainingLine(aBuf, &currChar, &line);
if (matchedLine || aContainsFileEnd) {
return Err(LogError(NS_ERROR_FILE_CORRUPTED,
"Failed to parse CC line %zu: `%s`", mCCLineNumber,
line.get()));
}
// We didn't actually complete reading the line
mCCLineNumber--;
MOZ_ASSERT(currChar == prevChar);
return currChar;
}
mCCFileProgress += currChar - prevChar;
return currChar;
}
// Up-to-date as of Jan 15, 2025.
static bool SwitchToGrayRoots(const nsCString& aLabel) {
if (aLabel.Equals("mAnonymousGlobalScopes[i]"_ns)) {
return true;
}
if (aLabel.Equals("active window global"_ns)) {
return true;
}
if (aLabel.Equals("mCallback"_ns)) {
return true;
}
if (aLabel.Equals("DOM expando object"_ns)) {
return true;
}
if (StringBeginsWith(aLabel, "XPCNativeInterface"_ns)) {
return true;
}
if (StringBeginsWith(aLabel, "XPCWrappedNative"_ns)) {
return true;
}
if (StringBeginsWith(aLabel, "XPCVariant"_ns)) {
return true;
}
if (StringBeginsWith(aLabel, "nsXPCWrappedJS"_ns)) {
return true;
}
return false;
}
Result<size_t, LogError>
CollectorLogAnalyzerBackground::IngestGarbageCollectorLog(
const nsACString& aBuf, bool aContainsFileEnd) {
size_t currChar = 0;
size_t prevChar = 0;
while (currChar < aBuf.Length()) {
mGCFileProgress += currChar - prevChar;
prevChar = currChar;
mGCLineNumber++;
if (SkipCommentLine(aBuf, &currChar)) {
continue;
}
if (mCurrentGCSection == GCLogSection::BlackRoots ||
mCurrentGCSection == GCLogSection::GrayRoots) {
if (MatchEndSection(aBuf, &currChar)) {
mCurrentGCSection = GCLogSection::Graph;
continue;
}
uint64_t ptr;
nsAutoCString label;
GCColor color;
if (ParseGCNode(aBuf, &currChar, &ptr, &color, &label)) {
NodeTableIndex node = MOZ_TRY(EnsureNode(ptr));
if (mCurrentGCSection == GCLogSection::BlackRoots &&
SwitchToGrayRoots(label)) {
mCurrentGCSection = GCLogSection::GrayRoots;
}
mNodeFlags[node] |= dom::CollectorNodeFlags_Binding::ROOT;
if (mCurrentGCSection == GCLogSection::GrayRoots) {
mNodeFlags[node] |= dom::CollectorNodeFlags_Binding::SOFT_ROOT;
MOZ_TRY(AppendToVector(mGCGrayRoots, node));
} else {
MOZ_TRY(AppendToVector(mGCRoots, node));
}
continue;
}
WeakMapEntry entry = {};
if (ParseWeakMapEntry(aBuf, &currChar, &entry)) {
MOZ_TRY(AddWeakMapEntry(entry));
continue;
}
} else if (mCurrentGCSection == GCLogSection::Graph) {
uint64_t ptr;
nsAutoCString label;
GCColor color;
if (ParseGCNode(aBuf, &currChar, &ptr, &color, &label)) {
mCurrentGCNode = MOZ_TRY(EnsureNode(ptr));
StringBufferIndex labelIndex = MOZ_TRY(InternString(label));
mNodeLabels[mCurrentGCNode] = labelIndex;
if (color == GCColor::Gray) {
mNodeFlags[mCurrentGCNode] |=
dom::CollectorNodeFlags_Binding::GC_MARKED;
mNodeFlags[mCurrentGCNode] |=
dom::CollectorNodeFlags_Binding::GC_GRAY;
} else if (color == GCColor::Black) {
mNodeFlags[mCurrentGCNode] |=
dom::CollectorNodeFlags_Binding::GC_MARKED;
}
if (mNodeEdges[mCurrentGCNode].mGC != INVALID_NODE) {
return Err(LogError(
NS_ERROR_FILE_CORRUPTED,
"Encountered node 0x%" PRIx64 " twice in the logs", ptr));
}
mNodeEdges[mCurrentGCNode].mGC = mEdges.length();
continue;
}
bool weak = false;
if (ParseGCEdge(aBuf, &currChar, &ptr, &weak, &label)) {
if (mCurrentGCNode >= mNodeEdges.length()) {
return Err(
LogError(NS_ERROR_FILE_CORRUPTED,
"Invalid log format: edge encountered before a node"));
}
if (weak) {
continue;
}
StringBufferIndex labelIndex = MOZ_TRY(InternString(label));
NodeTableIndex edge = MOZ_TRY(EnsureNode(ptr));
MOZ_TRY(AddGCEdge(mCurrentGCNode, edge, labelIndex));
continue;
}
} else {
MOZ_CRASH("Unexpected section");
}
nsAutoCString line;
if (MatchRemainingLine(aBuf, &currChar, &line) || aContainsFileEnd) {
return Err(LogError(NS_ERROR_FILE_CORRUPTED,
"Failed to parse GC line %zu: `%s`", mGCLineNumber,
line.get()));
}
// We didn't actually complete reading the line
mGCLineNumber--;
MOZ_ASSERT(currChar == prevChar);
return currChar;
}
mGCFileProgress += currChar - prevChar;
return currChar;
}
dom::CollectorLogNode CollectorLogAnalyzerBackground::MakeResultNode(
NodeTableIndex aIndex) {
dom::CollectorLogNode result;
NodeId id = mNodeIds[aIndex];
result.mIndex = aIndex;
result.mPtr = nsPrintfCString("0x%" PRIx64, id);
if (mNodeLabels[aIndex] != INVALID_STRING) {
result.mLabel = nsCString(&mStrings[mNodeLabels[aIndex]]);
}
auto ccRefCountPtr = mCCReferenceCounts.lookup(aIndex);
if (ccRefCountPtr) {
result.mReferenceCount = ccRefCountPtr->value();
} else {
result.mReferenceCount = -1;
}
result.mFlags = mNodeFlags[aIndex];
return result;
}
Result<nsTArray<dom::CollectorLogNode>, LogError>
CollectorLogAnalyzerBackground::QueryNodesImpl(const nsCString& aQuery) {
MOZ_TRY(EnsureInitialized());
HashSet<size_t> stringIndices = MOZ_TRY(FindStringIndices(mStrings, aQuery));
uint64_t bytePattern = 0;
size_t matchEnd = 0;
bool matchPtrs = false;
if (ParsePointer(aQuery, &matchEnd, &bytePattern) &&
matchEnd == aQuery.Length()) {
matchPtrs = true;
}
nsTArray<dom::CollectorLogNode> result;
nsTArray<dom::CollectorLogNode> garbage;
if (!matchPtrs && stringIndices.count() == 0) {
return result;
}
for (NodeTableIndex i = 0; i < mNodeLabels.length(); ++i) {
nsTArray<dom::CollectorLogNode>* dest = &result;
if (mNodeFlags[i] & dom::CollectorNodeFlags_Binding::GARBAGE) {
dest = &garbage;
}
NodeId id = mNodeIds[i];
StringBufferIndex label = mNodeLabels[i];
if (matchPtrs && id == bytePattern) {
dest->AppendElement(MakeResultNode(i));
continue;
}
if (stringIndices.has(label)) {
dest->AppendElement(MakeResultNode(i));
continue;
}
if (result.Length() >= MAX_QUERY_RESULTS) {
break;
}
}
size_t garbageIndex = 0;
while (result.Length() < MAX_QUERY_RESULTS &&
garbageIndex < garbage.Length()) {
result.AppendElement(garbage.ElementAt(garbageIndex++));
}
return result;
}
Result<nsTArray<dom::CollectorLogNode>, LogError>
CollectorLogAnalyzerBackground::SampleNodesImpl() {
MOZ_TRY(EnsureInitialized());
AutoTArray<dom::CollectorLogNode, SAMPLE_COUNT> result;
// Reservoir sampling. It's maybe a little overkill but if we ever want
// to sample with a filter this is nicely extendable.
for (NodeTableIndex i = 0; i < mNodeLabels.length(); ++i) {
if (mNodeFlags[i] & dom::CollectorNodeFlags_Binding::GARBAGE) {
continue;
}
if (result.Length() < SAMPLE_COUNT) {
result.AppendElement(MakeResultNode(i));
} else {
NodeId id = mNodeIds[i];
size_t randomEnough = HashGeneric(id);
size_t randomIndex = randomEnough % i;
if (randomIndex < SAMPLE_COUNT) {
result[randomIndex] = MakeResultNode(i);
}
}
}
return result;
}
Result<Ok, LogError> CollectorLogAnalyzerBackground::InitImpl(
const nsAString& aCCLogPath, const nsAString& aGCLogPath) {
mHaveCC = aCCLogPath.Length() > 0;
mHaveGC = aGCLogPath.Length() > 0;
mCCFileSize = 0;
mGCFileSize = 0;
int64_t totalCCFileSize = 0;
int64_t totalGCFileSize = 0;
nsCOMPtr<nsIFile> ccLogFile;
nsCOMPtr<nsIFile> gcLogFile;
nsresult rv = NS_OK;
if (mHaveCC) {
rv = NS_NewLocalFile(aCCLogPath, getter_AddRefs(ccLogFile));
if (NS_FAILED(rv)) {
return Err(LogError(rv, "NS_NewLocalFile failed for CC log"));
}
int64_t fileSize;
rv = ccLogFile->GetFileSize(&fileSize);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "GetFileSize failed for CC log"));
}
mCCFileSize = totalCCFileSize = fileSize;
}
if (mHaveGC) {
rv = NS_NewLocalFile(aGCLogPath, getter_AddRefs(gcLogFile));
if (NS_FAILED(rv)) {
return Err(LogError(rv, "NS_NewLocalFile failed for GC log"));
}
int64_t fileSize;
rv = gcLogFile->GetFileSize(&fileSize);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "GetFileSize failed for GC log"));
}
mGCFileSize = totalGCFileSize = fileSize;
}
int64_t maxChunkSize = 128 * 1024 * 1024;
size_t bufferSize = size_t(
std::min(maxChunkSize, std::max(totalCCFileSize, totalGCFileSize)));
auto buffer = MakeUnique<char[]>(bufferSize);
if (mHaveCC) {
RefPtr<nsFileRandomAccessStream> ccStream = new nsFileRandomAccessStream();
rv = ccStream->Init(ccLogFile, PR_RDONLY, 0, 0);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "Failed to open CC log file at `%s`",
ccLogFile->HumanReadablePath().get()));
}
int64_t offset = 0;
while (offset < totalCCFileSize) {
rv = ccStream->Seek(PR_SEEK_SET, offset);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "Failed to seek in CC log file"));
}
uint32_t toRead =
uint32_t(std::min(int64_t(bufferSize - 1), totalCCFileSize - offset));
uint32_t bytesRead = 0;
rv = ccStream->Read(buffer.get(), toRead, &bytesRead);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "Failed to read CC log file"));
}
if (bytesRead == 0) {
return Err(
LogError(NS_ERROR_FILE_CORRUPTED, "Unexpected end of CC file"));
}
buffer.get()[bytesRead] = '\0';
bool containsFileEnd = offset + int64_t(bytesRead) == totalCCFileSize;
size_t processed = MOZ_TRY(IngestCycleCollectorLog(
nsDependentCString(buffer.get(), bytesRead), containsFileEnd));
if (processed == 0) {
return Err(
LogError(NS_ERROR_FILE_CORRUPTED, "Failed to parse CC file"));
}
offset += int64_t(processed);
}
}
if (mHaveGC) {
RefPtr<nsFileRandomAccessStream> gcStream = new nsFileRandomAccessStream();
rv = gcStream->Init(gcLogFile, PR_RDONLY, 0, 0);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "Failed to open GC log file at `%s`",
gcLogFile->HumanReadablePath().get()));
}
int64_t offset = 0;
while (offset < totalGCFileSize) {
rv = gcStream->Seek(PR_SEEK_SET, offset);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "Failed to seek in GC log file"));
}
uint32_t toRead =
uint32_t(std::min(int64_t(bufferSize - 1), totalGCFileSize - offset));
uint32_t bytesRead = 0;
rv = gcStream->Read(buffer.get(), toRead, &bytesRead);
if (NS_FAILED(rv)) {
return Err(LogError(rv, "Failed to read GC log file"));
}
if (bytesRead == 0) {
return Err(
LogError(NS_ERROR_FILE_CORRUPTED, "Unexpected end of GC file"));
}
buffer.get()[bytesRead] = '\0';
bool containsFileEnd = offset + int64_t(bytesRead) == totalGCFileSize;
size_t processed = MOZ_TRY(IngestGarbageCollectorLog(
nsDependentCString(buffer.get(), bytesRead), containsFileEnd));
if (processed == 0) {
return Err(
LogError(NS_ERROR_FILE_CORRUPTED, "Failed to parse GC file"));
}
offset += int64_t(processed);
}
}
return FinishInitialization();
}
Result<Ok, LogError> CollectorLogAnalyzerBackground::FinishInitialization() {
// Free ingestion-only lookup tables now that parsing is complete.
mStringTable.clearAndCompact();
mNodeIdsToIndices.clearAndCompact();
mCCReferenceCounts.compact();
// Shrink all data vectors to their final sizes.
mNodeIds.shrinkStorageToFit();
mNodeLabels.shrinkStorageToFit();
mNodeFlags.shrinkStorageToFit();
mNodeEdges.shrinkStorageToFit();
mObservedReferenceCounts.shrinkStorageToFit();
mStrings.shrinkStorageToFit();
mGCRoots.shrinkStorageToFit();
mGCGrayRoots.shrinkStorageToFit();
mIncrementalRoots.shrinkStorageToFit();
// Sort weak map edges by source and record each source's first entry index.
// Ensuring they are contiguous for each source will let us efficiently search
// through weak map edges when traversing the graph.
std::sort(mWeakMapEdges.begin(), mWeakMapEdges.end(),
[](const WeakMapEdge& a, const WeakMapEdge& b) {
return a.source() < b.source();
});
for (size_t i = 0; i < mWeakMapEdges.length(); ++i) {
if (i == 0 || mWeakMapEdges[i].source() != mWeakMapEdges[i - 1].source()) {
MOZ_ASSERT(mNodeEdges[mWeakMapEdges[i].source()].mWeakMap ==
INVALID_NODE);
MOZ_ASSERT(mNodeEdges[mWeakMapEdges[i].source()].mWeakMapCount > 0);
mNodeEdges[mWeakMapEdges[i].source()].mWeakMap = i;
}
}
mQuerySize = mNodeEdges.length();
for (NodeTableIndex current = 0; current < mNodeEdges.length(); ++current) {
mQueryProgress++;
HashSet<NodeTableIndex> ccSeen;
const NodeEdgesDescriptor& edges = mNodeEdges[current];
for (size_t i = 0; i < edges.mCCCount; i++) {
NodeTableIndex edge = mEdges[edges.mCC + i];
if (ccSeen.has(edge)) {
continue;
}
MOZ_TRY(PutInSet(ccSeen, edge));
mObservedReferenceCounts[edge]++;
}
for (size_t i = 0; i < edges.mGCCount; i++) {
NodeTableIndex edge = mEdges[edges.mGC + i];
if (ccSeen.has(edge)) {
continue;
}
mObservedReferenceCounts[edge]++;
}
}
// Classify CC-managed roots as hard or soft based on observed vs declared RC.
for (NodeTableIndex current = 0; current < mNodeFlags.length(); ++current) {
if (mNodeFlags[current] & dom::CollectorNodeFlags_Binding::CC_MANAGED &&
mNodeFlags[current] & dom::CollectorNodeFlags_Binding::ROOT) {
auto rcPtr = mCCReferenceCounts.lookup(current);
uint32_t declaredRefCount = rcPtr ? rcPtr->value() : 0;
uint32_t observedRefCount = mObservedReferenceCounts[current];
if (observedRefCount >= declaredRefCount) {
mNodeFlags[current] &= ~dom::CollectorNodeFlags_Binding::ROOT;
mNodeFlags[current] |= dom::CollectorNodeFlags_Binding::SOFT_ROOT;
MOZ_TRY(AppendToVector(mCCSoftRoots, current));
} else {
MOZ_TRY(AppendToVector(mCCRoots, current));
}
}
}
mCCRoots.shrinkStorageToFit();
mCCSoftRoots.shrinkStorageToFit();
mInitialized = true;
return Ok();
}
struct PathNode {
NodeTableIndex mFrom;
NodeTableIndex mWeakMap;
uint64_t mDistance;
WeakMapEdgeKind mKind;
};
// BFS from roots to aNodeIndex, returning the shortest path.
// When aOnlyUseSoftRoots is false, searches from hard roots (GC black roots and
// CC roots with unexplained references) first. If no path is found, retries
// with aOnlyUseSoftRoots = true. When aOnlyUseSoftRoots is true, searches from
// soft roots (GC gray roots and CC roots whose references are fully accounted
// for) and returns None if no path is found.
Result<dom::CollectorLogRootPath, LogError>
CollectorLogAnalyzerBackground::GetPathToRootInner(NodeTableIndex aNodeIndex,
bool aOnlyUseSoftRoots) {
MOZ_TRY(EnsureInitialized());
dom::CollectorLogRootPath result;
HashMap<NodeTableIndex, PathNode> paths;
std::queue<NodeTableIndex> worklist;
if (aOnlyUseSoftRoots) {
for (NodeTableIndex root : mGCGrayRoots) {
PathNode node = {INVALID_NODE, 0, 0, WeakMapEdgeKind::None};
MOZ_TRY(PutInMap(paths, root, node));
worklist.push(root);
}
for (NodeTableIndex root : mCCSoftRoots) {
PathNode node = {INVALID_NODE, 0, 0, WeakMapEdgeKind::None};
MOZ_TRY(PutInMap(paths, root, node));
worklist.push(root);
}
} else {
for (NodeTableIndex root : mGCRoots) {
PathNode node = {INVALID_NODE, 0, 0, WeakMapEdgeKind::None};
MOZ_TRY(PutInMap(paths, root, node));
worklist.push(root);
}
for (NodeTableIndex root : mCCRoots) {
PathNode node = {INVALID_NODE, 0, 0, WeakMapEdgeKind::None};
MOZ_TRY(PutInMap(paths, root, node));
worklist.push(root);
}
}
// Incremental roots are objects touched during an incremental CC that must
// be treated as live; include them regardless of soft-root mode.
for (NodeTableIndex root : mIncrementalRoots) {
auto p = paths.lookupForAdd(root);
if (!p) {
PathNode node = {INVALID_NODE, 0, 0, WeakMapEdgeKind::None};
MOZ_TRY(AddToMap(paths, p, root, node));
worklist.push(root);
}
}
bool found = false;
while (!worklist.empty()) {
mQueryProgress++;
mQuerySize = mQueryProgress + worklist.size();
NodeTableIndex current = worklist.front();
worklist.pop();
auto pathLookup = paths.lookup(current);
if (!pathLookup) {
continue;
}
const PathNode& path = pathLookup->value();
uint64_t distance = path.mDistance;
uint64_t nextDistance = distance + 1;
if (current == aNodeIndex) {
found = true;
break;
}
const NodeEdgesDescriptor& edges = mNodeEdges[current];
for (size_t i = 0; i < edges.mCCCount; i++) {
NodeTableIndex edge = mEdges[edges.mCC + i];
auto p = paths.lookupForAdd(edge);
if (!p) {
PathNode edgeNode = {current, 0, nextDistance, WeakMapEdgeKind::None};
MOZ_TRY(AddToMap(paths, p, edge, edgeNode));
worklist.push(edge);
}
}
for (size_t i = 0; i < edges.mGCCount; i++) {
NodeTableIndex edge = mEdges[edges.mGC + i];
auto p = paths.lookupForAdd(edge);
if (!p) {
PathNode edgeNode = {current, 0, nextDistance, WeakMapEdgeKind::None};
MOZ_TRY(AddToMap(paths, p, edge, edgeNode));
worklist.push(edge);
}
}
for (size_t i = 0; i < edges.mWeakMapCount; i++) {
WeakMapEdge edge = mWeakMapEdges[edges.mWeakMap + i];
MOZ_ASSERT(edge.source() == current);
if (!paths.has(edge.other())) {
continue;
}
auto p = paths.lookupForAdd(edge.mValue);
if (!p) {
PathNode edgeNode = {edge.mKey, edge.mMap, nextDistance, edge.mKind};
MOZ_TRY(AddToMap(paths, p, edge.mValue, edgeNode));
worklist.push(edge.mValue);
}
}
}
if (aOnlyUseSoftRoots) {
if (found) {
result.mKind = dom::CollectorLogRootKind::Soft;
} else {
result.mKind = dom::CollectorLogRootKind::None;
}
} else {
if (found) {
result.mKind = dom::CollectorLogRootKind::Hard;
} else {
return GetPathToRootInner(aNodeIndex, /* aOnlyUseSoftRoots = */ true);
}
}
std::queue<NodeTableIndex> resultWorklist;
std::queue<NodeTableIndex> weakMapKeysToProcess;
resultWorklist.push(aNodeIndex);
HashSet<NodeTableIndex> processed;
MOZ_TRY(PutInSet(processed, aNodeIndex));
bool firstPath = true;
while (!resultWorklist.empty()) {
NodeTableIndex current = resultWorklist.front();
resultWorklist.pop();
nsTArray<dom::CollectorLogEdge> path;
HashMap<NodeTableIndex, PathNode>::Ptr pathLookup;
while ((pathLookup = paths.lookup(current))) {
const PathNode& pathNode = pathLookup->value();
dom::CollectorLogEdge edge;
edge.mOther = MakeResultNode(current);
if (pathNode.mFrom != INVALID_NODE) {
const NodeEdgesDescriptor& edges = mNodeEdges[pathNode.mFrom];
int64_t edgeIndex = -1;
for (size_t i = 0; i < edges.mCCCount; i++) {
if (mEdges[edges.mCC + i] == current) {
edgeIndex = int64_t(edges.mCC) + int64_t(i);
break;
}
}
if (edgeIndex == -1) {
for (size_t i = 0; i < edges.mGCCount; i++) {
if (mEdges[edges.mGC + i] == current) {
edgeIndex = int64_t(edges.mGC) + int64_t(i);
break;
}
}
}
if (edgeIndex != -1) {
edge.mLabel = nsCString(&mStrings[mEdgeLabels[edgeIndex]]);
}
}
path.AppendElement(edge);
current = pathNode.mFrom;
if (pathNode.mWeakMap && !processed.has(pathNode.mWeakMap)) {
MOZ_TRY(PutInSet(processed, pathNode.mWeakMap));
resultWorklist.push(pathNode.mWeakMap);
weakMapKeysToProcess.push(pathNode.mFrom);
}
}
std::reverse(path.begin(), path.end());
if (firstPath) {
result.mPath = std::move(path);
firstPath = false;
} else {
dom::CollectorLogWeakMapPath wmPath;
NodeTableIndex key = weakMapKeysToProcess.front();
weakMapKeysToProcess.pop();
wmPath.mKey = MakeResultNode(key);
wmPath.mPath = std::move(path);
if (!result.mWeakMapPaths.AppendElement(std::move(wmPath),
mozilla::fallible)) {
return Err(LogError(NS_ERROR_OUT_OF_MEMORY,
"Out of memory growing weak map paths"));
}
}
}
return result;
}
Result<dom::CollectorLogNodeAdjacents, LogError>
CollectorLogAnalyzerBackground::GetNodeAdjacentsImpl(
NodeTableIndex aNodeIndex) {
MOZ_TRY(EnsureInitialized());
if (aNodeIndex >= mNodeEdges.length()) {
return Err(LogError(NS_ERROR_ILLEGAL_INPUT,
"Invalid node supplied to getNodeAdjacents"));
}
mQuerySize = mNodeEdges.length() + mNodeEdges[aNodeIndex].mCCCount +
mNodeEdges[aNodeIndex].mGCCount;
mQueryProgress = 0;
nsTArray<dom::CollectorLogEdge> toSelf;
nsTArray<dom::CollectorLogEdge> fromSelf;
for (NodeTableIndex i = 0; i < mNodeEdges.length(); ++i) {
mQueryProgress++;
const NodeEdgesDescriptor& edges = mNodeEdges[i];
bool foundCC = false;
for (EdgeTableIndex j = 0; j < edges.mCCCount; ++j) {
if (mEdges[edges.mCC + j] == aNodeIndex) {
dom::CollectorLogEdge edge;
edge.mOther = MakeResultNode(i);
edge.mLabel = &mStrings[mEdgeLabels[edges.mCC + j]];
toSelf.AppendElement(edge);
foundCC = true;
}
}
// The GC log can contain edges to nodes which effectively
// are just duplicates of the edges already present in the
// CC log. As a best effort attempt to not confuse, we
// simply exclude GC edges from A -> B if we already have
// a CC-reported edge from A -> B
if (!foundCC) {
for (EdgeTableIndex j = 0; j < edges.mGCCount; ++j) {
if (mEdges[edges.mGC + j] == aNodeIndex) {
dom::CollectorLogEdge edge;
edge.mOther = MakeResultNode(i);
edge.mLabel = &mStrings[mEdgeLabels[edges.mGC + j]];
toSelf.AppendElement(edge);
break;
}
}
}
if (toSelf.Length() >= MAX_QUERY_RESULTS) {
break;
}
}
{
HashSet<NodeTableIndex> seen;
const NodeEdgesDescriptor& edges = mNodeEdges[aNodeIndex];
for (NodeTableIndex i = 0; i < edges.mCCCount; i++) {
if (fromSelf.Length() >= MAX_QUERY_RESULTS) {
break;
}
mQueryProgress++;
dom::CollectorLogEdge edge;
edge.mOther = MakeResultNode(mEdges[edges.mCC + i]);
edge.mLabel = &mStrings[mEdgeLabels[edges.mCC + i]];
fromSelf.AppendElement(edge);
MOZ_TRY(PutInSet(seen, mEdges[edges.mCC + i]));
}
for (NodeTableIndex i = 0; i < edges.mGCCount; i++) {
if (fromSelf.Length() >= MAX_QUERY_RESULTS) {
break;
}
mQueryProgress++;
if (!seen.has(mEdges[edges.mGC + i])) {
dom::CollectorLogEdge edge;
edge.mOther = MakeResultNode(mEdges[edges.mGC + i]);
edge.mLabel = &mStrings[mEdgeLabels[edges.mGC + i]];
fromSelf.AppendElement(edge);
}
}
}
dom::CollectorLogNodeAdjacents result;
result.mToSelf = std::move(toSelf);
result.mFromSelf = std::move(fromSelf);
return result;
}
already_AddRefed<dom::Promise> CollectorLogAnalyzer::Init(ErrorResult& aRv) {
return DispatchToBackground<Ok>(
aRv, [background = mBackground, ccLogPath = nsString(mCCLogPath),
gcLogPath = nsString(mGCLogPath)]() {
return background->InitImpl(ccLogPath, gcLogPath);
});
}
double CollectorLogAnalyzer::GetInitProgress() {
return mBackground->GetInitProgress();
}
already_AddRefed<dom::Promise> CollectorLogAnalyzer::QueryNodes(
const nsACString& aQuery, ErrorResult& aRv) {
return DispatchToBackground<nsTArray<dom::CollectorLogNode>>(
aRv, [background = mBackground, query = nsCString(aQuery)]() {
return background->QueryNodesImpl(query);
});
}
already_AddRefed<dom::Promise> CollectorLogAnalyzer::GetPathToRoot(
const dom::CollectorLogNode& aNode, ErrorResult& aRv) {
return DispatchToBackground<dom::CollectorLogRootPath>(
aRv, [background = mBackground, nodeIndex = aNode.mIndex]() {
return background->GetPathToRootImpl(nodeIndex);
});
}
already_AddRefed<dom::Promise> CollectorLogAnalyzer::GetNodeAdjacents(
const dom::CollectorLogNode& aNode, ErrorResult& aRv) {
return DispatchToBackground<dom::CollectorLogNodeAdjacents>(
aRv, [background = mBackground, nodeIndex = aNode.mIndex]() {
return background->GetNodeAdjacentsImpl(nodeIndex);
});
}
double CollectorLogAnalyzer::GetQueryProgress() {
return mBackground->GetQueryProgress();
}
already_AddRefed<dom::Promise> CollectorLogAnalyzer::SampleNodes(
ErrorResult& aRv) {
return DispatchToBackground<nsTArray<dom::CollectorLogNode>>(
aRv,
[background = mBackground]() { return background->SampleNodesImpl(); });
}
/* static */
already_AddRefed<CollectorLogAnalyzer> CollectorLogAnalyzer::Constructor(
dom::GlobalObject& aGlobal, const nsAString& aCCLogPath,
const nsAString& aGCLogPath) {
nsCOMPtr<nsIGlobalObject> globalSupports =
do_QueryInterface(aGlobal.GetAsSupports());
RefPtr<CollectorLogAnalyzer> analyzer =
new CollectorLogAnalyzer(globalSupports, aCCLogPath, aGCLogPath);
return analyzer.forget();
}
} // namespace mozilla