diff options
Diffstat (limited to 'src/ToolBox/SOS/Strike/gcroot.cpp')
-rw-r--r-- | src/ToolBox/SOS/Strike/gcroot.cpp | 2503 |
1 files changed, 2503 insertions, 0 deletions
diff --git a/src/ToolBox/SOS/Strike/gcroot.cpp b/src/ToolBox/SOS/Strike/gcroot.cpp new file mode 100644 index 0000000000..f68b935e21 --- /dev/null +++ b/src/ToolBox/SOS/Strike/gcroot.cpp @@ -0,0 +1,2503 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +// ==++== +// + +// +// ==--== + +/* + * This file defines the support classes that allow us to operate on the object graph of the process that SOS + * is analyzing. + * + * The GCRoot algorithm is based on three simple principles: + * 1. Only consider an object once. When we inspect an object, read its references and don't ever touch + * it again. This ensures that our upper bound on the amount of time we spend walking the object + * graph very quickly reaches resolution. The objects we've already inspected (and thus won't inspect + * again) is tracked by the mConsidered variable. + * 2. Be extremely careful about reads from the target process. We use a linear cache for reading from + * object data. We also cache everything about the method tables we read out of, as well as caching + * the GCDesc which is required to walk the object's references. + * 3. Use O(1) data structures for anything perf-critical. Almost all of the data structures we use to + * keep track of data have very fast lookups. For example, to keep track of the objects we've considered + * we use a unordered_set. Similarly to keep track of MethodTable data we use a unordered_map to track the + * mt -> mtinfo mapping. + */ + +#include "sos.h" +#include "disasm.h" + +#ifdef _ASSERTE +#undef _ASSERTE +#endif + +#define _ASSERTE(a) {;} + +#include "gcdesc.h" + +#include "safemath.h" + + +#ifdef _ASSERTE +#undef _ASSERTE +#endif + +#ifndef _ASSERTE +#ifdef _DEBUG +#define _ASSERTE(expr) \ + do { if (!(expr) ) { ExtErr("_ASSERTE fired:\n\t%s\n", #expr); if (IsDebuggerPresent()) DebugBreak(); } } while (0) +#else +#define _ASSERTE(x) +#endif +#endif // ASSERTE + +inline size_t ALIGN_DOWN( size_t val, size_t alignment ) +{ + // alignment must be a power of 2 for this implementation to work (need modulo otherwise) + _ASSERTE( 0 == (alignment & (alignment - 1)) ); + size_t result = val & ~(alignment - 1); + return result; +} + +inline void* ALIGN_DOWN( void* val, size_t alignment ) +{ + return (void*) ALIGN_DOWN( (size_t)val, alignment ); +} + +LinearReadCache::LinearReadCache(ULONG pageSize) + : mCurrPageStart(0), mPageSize(pageSize), mCurrPageSize(0), mPage(0) +{ + mPage = new BYTE[pageSize]; + ClearStats(); +} + +LinearReadCache::~LinearReadCache() +{ + if (mPage) + delete [] mPage; +} + +bool LinearReadCache::MoveToPage(TADDR addr, unsigned int size) +{ + if (size > mPageSize) + size = mPageSize; + + mCurrPageStart = addr; + HRESULT hr = g_ExtData->ReadVirtual(mCurrPageStart, mPage, size, &mCurrPageSize); + + if (hr != S_OK) + { + mCurrPageStart = 0; + mCurrPageSize = 0; + return false; + } + +#ifdef _DEBUG + mMisses++; +#endif + return true; +} + + +static const char *NameForHandle(unsigned int type) +{ + switch (type) + { + case 0: + return "weak short"; + case 1: + return "weak long"; + case 2: + return "strong"; + case 3: + return "pinned"; + case 5: + return "ref counted"; + case 6: + return "dependent"; + case 7: + return "async pinned"; + case 8: + return "sized ref"; + } + + return "unknown"; +} + +/////////////////////////////////////////////////////////////////////////////// +// GCRoot functions to cleanup data. +/////////////////////////////////////////////////////////////////////////////// +void GCRootImpl::ClearSizeData() +{ + mConsidered.clear(); + mSizes.clear(); +} + +void GCRootImpl::ClearAll() +{ + ClearNodes(); + + { + std::unordered_map<TADDR, MTInfo*>::iterator itr; + for (itr = mMTs.begin(); itr != mMTs.end(); ++itr) + delete itr->second; + } + + { + std::unordered_map<TADDR, RootNode*>::iterator itr; + for (itr = mTargets.begin(); itr != mTargets.end(); ++itr) + delete itr->second; + } + + mMTs.clear(); + mTargets.clear(); + mConsidered.clear(); + mSizes.clear(); + mDependentHandleMap.clear(); + mCache.ClearStats(); + + mAll = false; + mSize = false; +} + +void GCRootImpl::ClearNodes() +{ + std::list<RootNode*>::iterator itr; + + for (itr = mCleanupList.begin(); itr != mCleanupList.end(); ++itr) + delete *itr; + + mCleanupList.clear(); + mRootNewList.clear(); +} + +GCRootImpl::RootNode *GCRootImpl::NewNode(TADDR obj, MTInfo *mtInfo, bool fromDependent) +{ + // We need to create/destroy a TON of nodes during execution of GCRoot functions. + // To avoid heap fragmentation (and since it's faster), we don't actually new/delete + // nodes unless we have to. Instead we keep a stl list with free nodes to use. + RootNode *toReturn = NULL; + + if (mRootNewList.size()) + { + toReturn = mRootNewList.back(); + mRootNewList.pop_back(); + } + else + { + toReturn = new RootNode(); + mCleanupList.push_back(toReturn); + } + + toReturn->Object = obj; + toReturn->MTInfo = mtInfo; + toReturn->FromDependentHandle = fromDependent; + return toReturn; +} + +void GCRootImpl::DeleteNode(RootNode *node) +{ + // Add node to the "new list". + node->Clear(); + mRootNewList.push_back(node); +} + +void GCRootImpl::GetDependentHandleMap(std::unordered_map<TADDR, std::list<TADDR>> &map) +{ + unsigned int type = HNDTYPE_DEPENDENT; + ToRelease<ISOSHandleEnum> handles; + + HRESULT hr = g_sos->GetHandleEnumForTypes(&type, 1, &handles); + + if (FAILED(hr)) + { + ExtOut("Failed to walk dependent handles. GCRoot may miss paths.\n"); + return; + } + + SOSHandleData data[4]; + unsigned int fetched = 0; + + do + { + hr = handles->Next(_countof(data), data, &fetched); + + if (FAILED(hr)) + { + ExtOut("Error walking dependent handles. GCRoot may miss paths.\n"); + return; + } + + for (unsigned int i = 0; i < fetched; ++i) + { + if (data[i].Secondary != 0) + { + TADDR obj = 0; + TADDR target = TO_TADDR(data[i].Secondary); + + MOVE(obj, TO_TADDR(data[i].Handle)); + + map[obj].push_back(target); + } + } + } while (fetched == _countof(data)); +} + +/////////////////////////////////////////////////////////////////////////////// +// Public functions. +/////////////////////////////////////////////////////////////////////////////// +int GCRootImpl::PrintRootsForObject(TADDR target, bool all, bool noStacks) +{ + ClearAll(); + GetDependentHandleMap(mDependentHandleMap); + + mAll = all; + + // Add "target" to the mTargets list. + TADDR mt = ReadPointerCached(target); + RootNode *node = NewNode(target, GetMTInfo(mt)); + mTargets[target] = node; + + // Look for roots on the HandleTable, FQ, and all threads. + int count = 0; + + if (!noStacks) + count += PrintRootsOnAllThreads(); + + count += PrintRootsOnHandleTable(); + count += PrintRootsOnFQ(); + + if(count == 0) + { + count += PrintRootsOnFQ(true); + if(count) + { + ExtOut("Warning: These roots are from finalizable objects that are not yet ready for finalization.\n"); + ExtOut("This is to handle the case where objects re-register themselves for finalization.\n"); + ExtOut("These roots may be false positives.\n"); + } + } + + mCache.PrintStats(__FUNCTION__); + return count; +} + + +bool GCRootImpl::PrintPathToObject(TADDR root, TADDR target) +{ + ClearAll(); + GetDependentHandleMap(mDependentHandleMap); + + // Add "target" to the mTargets list. + TADDR mt = ReadPointerCached(target); + RootNode *node = NewNode(target, GetMTInfo(mt)); + mTargets[target] = node; + + // Check to see if the root reaches the target. + RootNode *path = FindPathToTarget(root); + if (path) + { + ExtOut("%p %S\n", SOS_PTR(path->Object), path->GetTypeName()); + path = path->Next; + + while (path) + { + ExtOut(" -> %p %S%s\n",SOS_PTR(path->Object), path->GetTypeName(), path->FromDependentHandle ? " (dependent handle)" : ""); + path = path->Next; + } + + mCache.PrintStats(__FUNCTION__); + return true; + } + + mCache.PrintStats(__FUNCTION__); + return false; +} + +size_t GCRootImpl::ObjSize(TADDR root) +{ + // Calculates the size of the closure of objects kept alive by root. + ClearAll(); + GetDependentHandleMap(mDependentHandleMap); + + // mSize tells GCRootImpl to build the "mSizes" table with the total size + // each object roots. + mSize = true; + + // Note that we are calling the same method as we would to locate the rooting + // chain for an object, but we haven't added any items to mTargets. This means + // the algorithm will scan all objects and never terminate until it has walked + // all objects in the closure. + FindPathToTarget(root); + + mCache.PrintStats(__FUNCTION__); + return mSizes[root]; +} + +void GCRootImpl::ObjSize() +{ + ClearAll(); + GetDependentHandleMap(mDependentHandleMap); + mSize = true; + + // Walks all roots in the process, and prints out the object size for each one. + PrintRootsOnAllThreads(); + PrintRootsOnHandleTable(); + PrintRootsOnFQ(); + + mCache.PrintStats(__FUNCTION__); +} + + +const std::unordered_set<TADDR> &GCRootImpl::GetLiveObjects(bool excludeFQ) +{ + ClearAll(); + GetDependentHandleMap(mDependentHandleMap); + + // Walk each root in the process without setting a target. This has the effect of + // causing us to walk every object in the process, adding them to mConsidered as we + // go. + PrintRootsOnAllThreads(); + PrintRootsOnHandleTable(); + + if (!excludeFQ) + PrintRootsOnFQ(); + + mCache.PrintStats(__FUNCTION__); + return mConsidered; +} + +int GCRootImpl::FindRoots(int gen, TADDR target) +{ + ClearAll(); + GetDependentHandleMap(mDependentHandleMap); + + if (gen == -1 || ((UINT)gen) == GetMaxGeneration()) + { + // If this is a gen 2 !FindRoots, just do a regular !GCRoot + return PrintRootsForObject(target, false, false); + } + else + { + // Otherwise walk all roots for only the given generation. + int count = PrintRootsInOlderGen(); + count += PrintRootsOnHandleTable(gen); + count += PrintRootsOnFQ(); + return count; + } +} + + + +/////////////////////////////////////////////////////////////////////////////// +// GCRoot Methods for printing out results. +/////////////////////////////////////////////////////////////////////////////// +void GCRootImpl::ReportSizeInfo(const SOSHandleData &handle, TADDR obj) +{ + // Print size for a handle (!objsize) + TADDR mt = ReadPointer(obj); + MTInfo *mtInfo = GetMTInfo(mt); + + const WCHAR *type = mtInfo ? mtInfo->GetTypeName() : W("unknown type"); + + size_t size = mSizes[obj]; + ExtOut("Handle (%s): %p -> %p: %d (0x%x) bytes (%S)\n", NameForHandle(handle.Type), SOS_PTR(handle.Handle), + SOS_PTR(obj), size, size, type); +} + + +void GCRootImpl::ReportSizeInfo(DWORD thread, const SOSStackRefData &stackRef, TADDR obj) +{ + // Print size for a stack root (!objsize) + WString frame; + if (stackRef.SourceType == SOS_StackSourceIP) + frame = MethodNameFromIP(stackRef.Source); + else + frame = GetFrameFromAddress(TO_TADDR(stackRef.Source)); + + WString regOutput = BuildRegisterOutput(stackRef); + + TADDR mt = ReadPointer(obj); + MTInfo *mtInfo = GetMTInfo(mt); + const WCHAR *type = mtInfo ? mtInfo->GetTypeName() : W("unknown type"); + + size_t size = mSizes[obj]; + ExtOut("Thread %x (%S): %S: %d (0x%x) bytes (%S)\n", thread, frame.c_str(), regOutput.c_str(), size, size, type); +} + +void GCRootImpl::ReportOneHandlePath(const SOSHandleData &handle, RootNode *path, bool printHeader) +{ + if (printHeader) + ExtOut("HandleTable:\n"); + + ExtOut(" %p (%s handle)\n", SOS_PTR(handle.Handle), NameForHandle(handle.Type)); + while (path) + { + ExtOut(" -> %p %S%s\n", SOS_PTR(path->Object), path->GetTypeName(), path->FromDependentHandle ? " (dependent handle)" : ""); + path = path->Next; + } + + ExtOut("\n"); +} + +void GCRootImpl::ReportOnePath(DWORD thread, const SOSStackRefData &stackRef, RootNode *path, bool printThread, bool printFrame) +{ + if (printThread) + ExtOut("Thread %x:\n", thread); + + if (printFrame) + { + if (stackRef.SourceType == SOS_StackSourceIP) + { + WString methodName = MethodNameFromIP(stackRef.Source); + ExtOut(" %p %p %S\n", SOS_PTR(stackRef.StackPointer), SOS_PTR(stackRef.Source), methodName.c_str()); + } + else + { + WString frameName = GetFrameFromAddress(TO_TADDR(stackRef.Source)); + ExtOut(" %p %S\n", SOS_PTR(stackRef.Source), frameName.c_str()); + } + } + + WString regOutput = BuildRegisterOutput(stackRef, false); + ExtOut(" %S\n", regOutput.c_str()); + + while (path) + { + ExtOut(" -> %p %S%s\n", SOS_PTR(path->Object), path->GetTypeName(), path->FromDependentHandle ? " (dependent handle)" : ""); + path = path->Next; + } + + ExtOut("\n"); +} + +void GCRootImpl::ReportOneFQEntry(TADDR root, RootNode *path, bool printHeader) +{ + if (printHeader) + ExtOut("Finalizer Queue:\n"); + + ExtOut(" %p\n", SOS_PTR(root)); + while (path) + { + ExtOut(" -> %p %S%s\n", SOS_PTR(path->Object), path->GetTypeName(), path->FromDependentHandle ? " (dependent handle)" : ""); + path = path->Next; + } + + ExtOut("\n"); +} + +void GCRootImpl::ReportOlderGenEntry(TADDR root, RootNode *path, bool printHeader) +{ + if (printHeader) + ExtOut("Older Generation:\n"); + + ExtOut(" %p\n", SOS_PTR(root)); + while (path) + { + ExtOut(" -> %p %S%s\n", SOS_PTR(path->Object), path->GetTypeName(), path->FromDependentHandle ? " (dependent handle)" : ""); + path = path->Next; + } + + ExtOut("\n"); +} + +////////////////////////////////////////////////////// +int GCRootImpl::PrintRootsInOlderGen() +{ + // Use a different linear read cache here instead of polluting the object read cache. + LinearReadCache cache(512); + + if (!IsServerBuild()) + { + DacpGcHeapAnalyzeData analyzeData; + if (analyzeData.Request(g_sos) != S_OK) + { + ExtErr("Error requesting gc heap analyze data\n"); + return 0; + } + + if (!analyzeData.heap_analyze_success) + { + ExtOut("Failed to gather needed data, possibly due to memory contraints in the debuggee.\n"); + ExtOut("To try again re-issue the !FindRoots -gen <N> command.\n"); + return 0; + } + + ExtDbgOut("internal_root_array = %#p\n", SOS_PTR(analyzeData.internal_root_array)); + ExtDbgOut("internal_root_array_index = %#p\n", SOS_PTR(analyzeData.internal_root_array_index)); + + TADDR start = TO_TADDR(analyzeData.internal_root_array); + TADDR stop = TO_TADDR(analyzeData.internal_root_array + sizeof(TADDR) * (size_t)analyzeData.internal_root_array_index); + + return PrintRootsInRange(cache, start, stop, &GCRootImpl::ReportOlderGenEntry, true); + } + else + { + int total = 0; + DWORD dwAllocSize; + DWORD dwNHeaps = GetGcHeapCount(); + if (!ClrSafeInt<DWORD>::multiply(sizeof(CLRDATA_ADDRESS), dwNHeaps, dwAllocSize)) + { + ExtErr("Failed to get GCHeaps: integer overflow\n"); + return 0; + } + + CLRDATA_ADDRESS *heapAddrs = (CLRDATA_ADDRESS*)alloca(dwAllocSize); + if (g_sos->GetGCHeapList(dwNHeaps, heapAddrs, NULL) != S_OK) + { + ExtErr("Failed to get GCHeaps\n"); + return 0; + } + + for (UINT n = 0; n < dwNHeaps; n ++) + { + DacpGcHeapAnalyzeData analyzeData; + if (analyzeData.Request(g_sos, heapAddrs[n]) != S_OK) + { + ExtErr("Error requesting gc heap analyze data for heap %p\n", SOS_PTR(heapAddrs[n])); + continue; + } + + if (!analyzeData.heap_analyze_success) + { + ExtOut("Failed to gather needed data, possibly due to memory contraints in the debuggee.\n"); + ExtOut("To try again re-issue the !FindRoots -gen <N> command.\n"); + continue; + } + + ExtDbgOut("internal_root_array = %#p\n", SOS_PTR(analyzeData.internal_root_array)); + ExtDbgOut("internal_root_array_index = %#p\n", SOS_PTR(analyzeData.internal_root_array_index)); + + TADDR start = TO_TADDR(analyzeData.internal_root_array); + TADDR stop = TO_TADDR(analyzeData.internal_root_array + sizeof(TADDR) * (size_t)analyzeData.internal_root_array_index); + + total += PrintRootsInRange(cache, start, stop, &GCRootImpl::ReportOlderGenEntry, total == 0); + } + + return total; + } +} + + +int GCRootImpl::PrintRootsOnFQ(bool notReadyForFinalization) +{ + // Here are objects kept alive by objects in the finalizer queue. + DacpGcHeapDetails heapDetails; + + // Use a different linear read cache here instead of polluting the object read cache. + LinearReadCache cache(512); + + if (!IsServerBuild()) + { + if (heapDetails.Request(g_sos) != S_OK) + { + ExtErr("Error requesting heap data.\n"); + return 0; + } + + // If we include objects that are not ready for finalization, we may report + // false positives. False positives occur if the object is not ready for finalization + // and does not re-register itself for finalization inside the finalizer. + TADDR start = 0; + TADDR stop = 0; + if(notReadyForFinalization) + { + start = TO_TADDR(SegQueue(heapDetails, gen_segment(GetMaxGeneration()))); + stop = TO_TADDR(SegQueueLimit(heapDetails, CriticalFinalizerListSeg)); + } + else + { + start = TO_TADDR(SegQueue(heapDetails, CriticalFinalizerListSeg)); + stop = TO_TADDR(SegQueue(heapDetails, FinalizerListSeg)); + } + + return PrintRootsInRange(cache, start, stop, &GCRootImpl::ReportOneFQEntry, true); + } + else + { + DWORD dwAllocSize; + DWORD dwNHeaps = GetGcHeapCount(); + if (!ClrSafeInt<DWORD>::multiply(sizeof(CLRDATA_ADDRESS), dwNHeaps, dwAllocSize)) + { + ExtErr("Failed to get GCHeaps: integer overflow\n"); + return 0; + } + + CLRDATA_ADDRESS *heapAddrs = (CLRDATA_ADDRESS*)alloca(dwAllocSize); + if (g_sos->GetGCHeapList(dwNHeaps, heapAddrs, NULL) != S_OK) + { + ExtErr("Error requesting heap data.\n"); + return 0; + } + + int total = 0; + for (UINT n = 0; n < dwNHeaps; n ++) + { + if (heapDetails.Request(g_sos, heapAddrs[n]) != S_OK) + { + ExtErr("Error requesting heap data for heap %d.\n", n); + continue; + } + + // If we include objects that are not ready for finalization, we may report + // false positives. False positives occur if the object is not ready for finalization + // and does not re-register itself for finalization inside the finalizer. + TADDR start = 0; + TADDR stop = 0; + if(notReadyForFinalization) + { + start = TO_TADDR(SegQueue(heapDetails, gen_segment(GetMaxGeneration()))); + stop = TO_TADDR(SegQueueLimit(heapDetails, CriticalFinalizerListSeg)); + } + else + { + start = TO_TADDR(SegQueue(heapDetails, CriticalFinalizerListSeg)); + stop = TO_TADDR(SegQueueLimit(heapDetails, FinalizerListSeg)); + } + + total += PrintRootsInRange(cache, start, stop, &GCRootImpl::ReportOneFQEntry, total == 0); + } + + return total; + } +} + +int GCRootImpl::PrintRootsInRange(LinearReadCache &cache, TADDR start, TADDR stop, ReportCallback func, bool printHeader) +{ + int total = 0; + + // Walk the range [start, stop) and consider each pointer in the range as a root. + while (start < stop) + { + if (IsInterrupt()) + return total; + + // Use the cache parameter here instead of mCache. If you use mCache it will be reset + // when calling into FindPathToTarget. + TADDR root = 0; + bool res = cache.Read(start, &root, true); + + if (res && root) + { + RootNode *path = FindPathToTarget(root); + if (path) + { + func(root, path, printHeader); + total++; + printHeader = false; + } + } + + start += sizeof(TADDR); + } + + return total; +} + +int GCRootImpl::PrintRootsOnAllThreads() +{ + ArrayHolder<DWORD_PTR> threadList = NULL; + int numThreads = 0; + + // GetThreadList calls ReportOOM so we don't need to do that here. + HRESULT hr = GetThreadList(&threadList, &numThreads); + if (FAILED(hr) || !threadList) + return 0; + + // Walk each thread and process the roots on it. + int total = 0; + DacpThreadData vThread; + for (int i = 0; i < numThreads; i++) + { + if (IsInterrupt()) + return total; + + if (FAILED(vThread.Request(g_sos, threadList[i]))) + continue; + + if (vThread.osThreadId) + total += PrintRootsOnThread(vThread.osThreadId); + } + + return total; +} + +int GCRootImpl::PrintRootsOnThread(DWORD osThreadId) +{ + // Grab all object rootson the thread. + unsigned int refCount = 0; + ArrayHolder<SOSStackRefData> refs = NULL; + + int total = 0; + bool first = true; + if (FAILED(::GetGCRefs(osThreadId, &refs, &refCount, NULL, NULL))) + { + ExtOut("Failed to walk thread %x\n", osThreadId); + return total; + } + + // Walk each non-null root, find if it contains a path to the target, + // and if so print it out. + CLRDATA_ADDRESS prevSource = 0, prevSP = 0; + for (unsigned int i = 0; i < refCount; ++i) + { + if (IsInterrupt()) + return total; + + if (refs[i].Object) + { + if (mSize) + ClearSizeData(); + + RootNode *path = FindPathToTarget(TO_TADDR(refs[i].Object)); + if (path) + { + bool reportFrame = refs[i].Source != prevSource || refs[i].StackPointer != prevSP; + ReportOnePath(osThreadId, refs[i], path, first, reportFrame); + first = false; + total++; + } + + if (mSize) + ReportSizeInfo(osThreadId, refs[i], TO_TADDR(refs[i].Object)); + } + } + + return total; +} + +int GCRootImpl::PrintRootsOnHandleTable(int gen) +{ + // Get handle data. + ToRelease<ISOSHandleEnum> pEnum = NULL; + HRESULT hr = S_OK; + + if (gen == -1 || (ULONG)gen == GetMaxGeneration()) + hr = g_sos->GetHandleEnum(&pEnum); + else + hr = g_sos->GetHandleEnumForGC(gen, &pEnum); + + if (FAILED(hr)) + { + ExtOut("Failed to walk the HandleTable!\n"); + return 0; + } + + int total = 0; + unsigned int fetched = 0; + SOSHandleData handles[8]; + + bool printHeader = true; + do + { + // Fetch more handles + hr = pEnum->Next(_countof(handles), handles, &fetched); + if (FAILED(hr)) + { + ExtOut("Failed to request more handles."); + return total; + } + + // Find rooting info for each handle. + for (unsigned int i = 0; i < fetched; ++i) + { + if (IsInterrupt()) + return total; + + // Ignore handles which aren't actually roots. + if (!handles[i].StrongReference) + continue; + + // clear the size table + if (mAll) + ClearSizeData(); + + // Get the object the handle points to. + TADDR root = ReadPointer(TO_TADDR(handles[i].Handle)); + + // Only inspect handle if the object is non-null, and not one we've already walked. + if (root) + { + // Find all paths to the object and don't clean up the return value. + // It's tracked by mCleanupList. + RootNode *path = FindPathToTarget(root); + if (path) + { + ReportOneHandlePath(handles[i], path, printHeader); + printHeader = false; + total++; + } + + if (mSize) + ReportSizeInfo(handles[i], root); + } + } + } + while (_countof(handles) == fetched); + + return total; +} + +GCRootImpl::RootNode *GCRootImpl::FilterRoots(RootNode *&list) +{ + // Filter the list of GC refs: + // - Remove objects that we have already considered + // - Check to see if we've located the target object (or an object which points to the target). + RootNode *curr = list; + RootNode *keep = NULL; + + while (curr) + { + // We don't check for Control-C in this loop to avoid inconsistent data. + RootNode *curr_next = curr->Next; + + std::unordered_map<TADDR, RootNode *>::iterator targetItr = mTargets.find(curr->Object); + if (targetItr != mTargets.end()) + { + // We found the object we are looking for (or an object which points to it)! + // Return the target, propogate whether we got the target from a dependent handle. + targetItr->second->FromDependentHandle = curr->FromDependentHandle; + return targetItr->second; + } + else if (mConsidered.find(curr->Object) != mConsidered.end()) + { + curr->Remove(list); + + DeleteNode(curr); + } + + curr = curr_next; + } + + return NULL; +} + +/* This is the core of the GCRoot algorithm. It is: + * 1. Start with a list of "targets" (objects we are trying to find the roots for) and a root + * in the process. + * 2. Let the root be "curr". + * 3. Find all objects curr points to and place them in curr->GCRefs (a linked list). + * 4. Walk curr->GCRefs. If we find any of the "targets", return the current path. If not, + * filter out any objects we've already considered (the mConsidered set). + * 5. Look at curr->GCRefs: + * 5a. If curr->GCRefs is NULL then we have walked all references of this object. Pop "curr" + * from the current path (curr = curr->Prev). If curr is NULL, we walked all objects and + * didn't find a target, return NULL. If curr is non-null, goto 5. + * 5b. If curr->GCRefs is non-NULL, pop one entry and push it onto the path (that is: + * curr->Next = curr->GCRefs; curr = curr->Next; curr->GCRefs = curr->GCRefs->Next) + * 6. Goto 3. + */ +GCRootImpl::RootNode *GCRootImpl::FindPathToTarget(TADDR root) +{ + // Early out. We may have already looked at this object. + std::unordered_map<TADDR, RootNode *>::iterator targetItr = mTargets.find(root); + if (targetItr != mTargets.end()) + return targetItr->second; + else if (mConsidered.find(root) != mConsidered.end()) + return NULL; + + // Add obj as a considered node (since we are considering it now). + mConsidered.insert(root); + + // Create path. + RootNode *path = NewNode(root); + + RootNode *curr = path; + while (curr) + { + if (IsInterrupt()) + return NULL; + + // If this is a new reference we are walking, we haven't filled the list of objects + // this one points to. Update that first. + if (!curr->FilledRefs) + { + // Get the list of GC refs. + curr->GCRefs = GetGCRefs(path, curr); + + // Filter the refs to remove objects we've already inspected. + RootNode *foundTarget = FilterRoots(curr->GCRefs); + + // If we've found the target, great! Return the path to the target. + if (foundTarget) + { + // Link the current to the target. + curr->Next = foundTarget; + foundTarget->Prev = curr; + + // If the user requested all paths, set each node in the path to be a target. + // Normally, we don't consider a node we've already seen, which means if we don't + // get a *completely* unique path, it's not printed out. By adding each of the + // nodes in the paths we find as potential targets, it prints out *every* path + // to the target, including ones with duplicate nodes. This is much slower. + if (mAll) + { + RootNode *tmp = path; + + while (tmp) + { + if (mTargets.find(tmp->Object) != mTargets.end()) + break; + + mTargets[tmp->Object] = tmp; + tmp = tmp->Next; + } + } + + return path; + } + } + + // We have filled the references, now walk them depth-first. + if (curr->GCRefs) + { + RootNode *next = curr->GCRefs; + curr->GCRefs = next->Next; + + if (mConsidered.find(next->Object) != mConsidered.end()) + { + // Whoops. This object was considered deeper down the tree, so we + // don't need to do it again. Delete this node and continue looping. + DeleteNode(next); + } + else + { + // Clear associations. + if (curr->GCRefs) + curr->GCRefs->Prev = NULL; + + next->Next = NULL; + + // Link curr and next, make next the current node. + curr->Next = next; + next->Prev = curr; + curr = next; + + // Finally, insert the current object into the considered set. + mConsidered.insert(curr->Object); + // Now the next iteration will operate on "next". + } + } + else + { + // This object has no more GCRefs. We now need to "pop" it from the current path. + RootNode *tmp = curr; + curr = curr->Prev; + DeleteNode(tmp); + } + } + + return NULL; +} + + +GCRootImpl::RootNode *GCRootImpl::GetGCRefs(RootNode *path, RootNode *node) +{ + // If this node doesn't have the method table ready, fill it out + TADDR obj = node->Object; + if (!node->MTInfo) + { + TADDR mt = ReadPointerCached(obj); + MTInfo *mtInfo = GetMTInfo(mt); + node->MTInfo = mtInfo; + } + + node->FilledRefs = true; + + // MTInfo can be null if we encountered an error reading out of the target + // process, just early out here as if it has no references. + if (!node->MTInfo) + return NULL; + + // Only calculate the size if we need it. + size_t objSize = 0; + if (mSize || node->MTInfo->ContainsPointers) + { + objSize = GetSizeOfObject(obj, node->MTInfo); + + // Update object size list, if requested. + if (mSize) + { + mSizes[obj] = 0; + + while (path) + { + mSizes[path->Object] += objSize; + path = path->Next; + } + } + } + + // Early out: If the object doesn't contain any pointers, return. + if (!node->MTInfo->ContainsPointers) + return NULL; + + // Make sure we have the object's data in the cache. + mCache.EnsureRangeInCache(obj, (unsigned int)objSize); + + // Storage for the gc refs. + RootNode *refs = NewNode(); + RootNode *curr = refs; + + // Walk the GCDesc, fill "refs" with non-null references. + CGCDesc *gcdesc = node->MTInfo->GCDesc; + bool aovc = node->MTInfo->ArrayOfVC; + for (sos::RefIterator itr(obj, gcdesc, aovc, &mCache); itr; ++itr) + { + if (*itr) + { + curr->Next = NewNode(*itr); + curr->Next->Prev = curr; + curr = curr->Next; + } + } + + // Add edges from dependent handles. + std::unordered_map<TADDR, std::list<TADDR>>::iterator itr = mDependentHandleMap.find(obj); + if (itr != mDependentHandleMap.end()) + { + for (std::list<TADDR>::iterator litr = itr->second.begin(); litr != itr->second.end(); ++litr) + { + curr->Next = NewNode(*litr, NULL, true); + curr->Next->Prev = curr; + curr = curr->Next; + } + } + + // The gcrefs actually start on refs->Next. + curr = refs; + refs = refs->Next; + DeleteNode(curr); + + return refs; +} + +DWORD GCRootImpl::GetComponents(TADDR obj, TADDR mt) +{ + // Get the number of components in the object (for arrays and such). + DWORD Value = 0; + + // If we fail to read out the number of components, let's assume 0 so we don't try to + // read further data from the object. + if (!mCache.Read(obj + sizeof(TADDR), &Value, false)) + return 0; + + // The component size on a String does not contain the trailing NULL character, + // so we must add that ourselves. + if(TO_TADDR(g_special_usefulGlobals.StringMethodTable) == mt) + return Value+1; + + return Value; +} + +// Get the size of the object. +size_t GCRootImpl::GetSizeOfObject(TADDR obj, MTInfo *info) +{ + size_t res = info->BaseSize; + + if (info->ComponentSize) + { + // this is an array, so the size has to include the size of the components. We read the number + // of components from the target and multiply by the component size to get the size. + DWORD components = GetComponents(obj, info->MethodTable); + res += info->ComponentSize * components; + } + +#ifdef _TARGET_WIN64_ + // On x64 we do an optimization to save 4 bytes in almost every string we create, so + // pad to min object size if necessary. + if (res < min_obj_size) + res = min_obj_size; +#endif // _TARGET_WIN64_ + + return (res > 0x10000) ? AlignLarge(res) : Align(res); +} + +GCRootImpl::MTInfo *GCRootImpl::GetMTInfo(TADDR mt) +{ + // Remove lower bits in case we are in mark phase + mt &= ~3; + + // Do we already have this MethodTable? + std::unordered_map<TADDR, MTInfo *>::iterator itr = mMTs.find(mt); + + if (itr != mMTs.end()) + return itr->second; + + MTInfo *curr = new MTInfo; + curr->MethodTable = mt; + + // Get Base/Component size. + DacpMethodTableData dmtd; + + if (dmtd.Request(g_sos, mt) != S_OK) + { + delete curr; + return NULL; + } + + // Fill out size info. + curr->BaseSize = (size_t)dmtd.BaseSize; + curr->ComponentSize = (size_t)dmtd.ComponentSize; + curr->ContainsPointers = dmtd.bContainsPointers ? true : false; + + // If this method table contains pointers, fill out and cache the GCDesc. + if (curr->ContainsPointers) + { + int nEntries; + + if (FAILED(MOVE(nEntries, mt-sizeof(TADDR)))) + { + ExtOut("Failed to request number of entries."); + delete curr; + return NULL; + } + + if (nEntries < 0) + { + curr->ArrayOfVC = true; + nEntries = -nEntries; + } + else + { + curr->ArrayOfVC = false; + } + + size_t nSlots = 1 + nEntries * sizeof(CGCDescSeries)/sizeof(TADDR); + curr->Buffer = new TADDR[nSlots]; + + if (curr->Buffer == NULL) + { + ReportOOM(); + delete curr; + return NULL; + } + + if (FAILED(g_ExtData->ReadVirtual(TO_CDADDR(mt - nSlots*sizeof(TADDR)), curr->Buffer, (ULONG)(nSlots*sizeof(TADDR)), NULL))) + { + ExtOut("Failed to read GCDesc for MethodTable %p.\n", SOS_PTR(mt)); + delete curr; + return NULL; + } + + // Construct the GCDesc map and series. + curr->GCDesc = (CGCDesc *)(curr->Buffer+nSlots); + } + + mMTs[mt] = curr; + return curr; +} + + +TADDR GCRootImpl::ReadPointer(TADDR location) +{ + // Reads a pointer from the cache, but doesn't update the cache if it wasn't in it. + TADDR obj = NULL; + bool res = mCache.Read(location, &obj, false); + + if (!res) + return NULL; + + return obj; +} + +TADDR GCRootImpl::ReadPointerCached(TADDR location) +{ + // Reads a pointer from the cache, but updates the cache if it wasn't in it. + TADDR obj = NULL; + bool res = mCache.Read(location, &obj, true); + + if (!res) + return NULL; + + return obj; +} + +/////////////////////////////////////////////////////////////////////////////// + +UINT FindAllPinnedAndStrong(DWORD_PTR handlearray[], UINT arraySize) +{ + unsigned int fetched = 0; + SOSHandleData data[64]; + UINT pos = 0; + + // We do not call GetHandleEnumByType here with a list of strong handles since we would be + // statically setting the list of strong handles, which could change in a future release. + // Instead we rely on the dac to provide whether a handle is strong or not. + ToRelease<ISOSHandleEnum> handles; + HRESULT hr = g_sos->GetHandleEnum(&handles); + if (FAILED(hr)) + { + // This should basically never happen unless there's an OOM. + ExtOut("Failed to enumerate GC handles. HRESULT=%x.\n", hr); + return 0; + } + + do + { + hr = handles->Next(_countof(data), data, &fetched); + + if (FAILED(hr)) + { + ExtOut("Failed to enumerate GC handles. HRESULT=%x.\n", hr); + break; + } + + for (unsigned int i = 0; i < fetched; ++i) + { + if (pos >= arraySize) + { + ExtOut("Buffer overflow while enumerating handles.\n"); + return pos; + } + + if (data[i].StrongReference) + { + handlearray[pos++] = (DWORD_PTR)data[i].Handle; + } + } + } while (fetched == _countof(data)); + + return pos; +} + + + +void PrintNotReachableInRange(TADDR rngStart, TADDR rngEnd, BOOL bExcludeReadyForFinalization, HeapStat* hpstat, BOOL bShort) +{ + GCRootImpl gcroot; + const std::unordered_set<TADDR> &liveObjs = gcroot.GetLiveObjects(bExcludeReadyForFinalization == TRUE); + + LinearReadCache cache(512); + cache.EnsureRangeInCache(rngStart, (unsigned int)(rngEnd-rngStart)); + + for (TADDR p = rngStart; p < rngEnd; p += sizeof(TADDR)) + { + if (IsInterrupt()) + break; + + TADDR header = 0; + TADDR obj = 0; + TADDR taddrMT = 0; + + bool read = cache.Read(p-sizeof(SIZEOF_OBJHEADER), &header); + read = read && cache.Read(p, &obj); + if (read && ((header & BIT_SBLK_FINALIZER_RUN) == 0) && liveObjs.find(obj) == liveObjs.end()) + { + if (bShort) + { + DMLOut("%s\n", DMLObject(obj)); + } + else + { + DMLOut("%s ", DMLObject(obj)); + if (SUCCEEDED(GetMTOfObject(obj, &taddrMT)) && taddrMT) + { + size_t s = ObjectSize(obj); + if (hpstat) + { + hpstat->Add(taddrMT, (DWORD)s); + } + } + } + } + } + + if (!bShort) + ExtOut("\n"); +} + + +//////////////////////////////////////////////////////////////////////////////// +// +// Some defines for cards taken from gc code +// +#define card_word_width ((size_t)32) + +// +// The value of card_size is determined empirically according to the average size of an object +// In the code we also rely on the assumption that one card_table entry (DWORD) covers an entire os page +// +#if defined (_TARGET_WIN64_) +#define card_size ((size_t)(2*DT_OS_PAGE_SIZE/card_word_width)) +#else +#define card_size ((size_t)(DT_OS_PAGE_SIZE/card_word_width)) +#endif //_TARGET_WIN64_ + +// so card_size = 128 on x86, 256 on x64 + +inline +size_t card_word (size_t card) +{ + return card / card_word_width; +} + +inline +unsigned card_bit (size_t card) +{ + return (unsigned)(card % card_word_width); +} + +inline +size_t card_of ( BYTE* object) +{ + return (size_t)(object) / card_size; +} + +BOOL CardIsSet(const DacpGcHeapDetails &heap, TADDR objAddr) +{ + // The card table has to be translated to look at the refcount, etc. + // g_card_table[card_word(card_of(g_lowest_address))]. + + TADDR card_table = TO_TADDR(heap.card_table); + card_table = card_table + card_word(card_of((BYTE *)heap.lowest_address))*sizeof(DWORD); + + do + { + TADDR card_table_lowest_addr; + TADDR card_table_next; + + if (MOVE(card_table_lowest_addr, ALIGN_DOWN(card_table, 0x1000) + sizeof(PVOID)) != S_OK) + { + ExtErr("Error getting card table lowest address\n"); + return FALSE; + } + + if (MOVE(card_table_next, card_table - sizeof(PVOID)) != S_OK) + { + ExtErr("Error getting next card table\n"); + return FALSE; + } + + size_t card = (objAddr - card_table_lowest_addr) / card_size; + DWORD value; + if (MOVE(value, card_table + card_word(card)*sizeof(DWORD)) != S_OK) + { + ExtErr("Error reading card bits\n"); + return FALSE; + } + + if (value & 1<<card_bit(card)) + return TRUE; + + card_table = card_table_next; + } + while(card_table); + + return FALSE; +} + +BOOL NeedCard(TADDR parent, TADDR child) +{ + int iChildGen = g_snapshot.GetGeneration(child); + + if (iChildGen == 2) + return FALSE; + + int iParentGen = g_snapshot.GetGeneration(parent); + + return (iChildGen < iParentGen); +} + +//////////////////////////////////////////////////////////////////////////////// +// +// Some defines for mark_array taken from gc code +// + +#define mark_bit_pitch 8 +#define mark_word_width 32 +#define mark_word_size (mark_word_width * mark_bit_pitch) +#define heap_segment_flags_swept 16 + +inline +size_t mark_bit_bit_of(CLRDATA_ADDRESS add) +{ + return (size_t)((add / mark_bit_pitch) % mark_word_width); +} + +inline +size_t mark_word_of(CLRDATA_ADDRESS add) +{ + return (size_t)(add / mark_word_size); +} + +inline BOOL mark_array_marked(const DacpGcHeapDetails &heap, CLRDATA_ADDRESS add) +{ + + DWORD entry = 0; + HRESULT hr = MOVE(entry, heap.mark_array + sizeof(DWORD) * mark_word_of(add)); + + if (FAILED(hr)) + ExtOut("Failed to read card table entry.\n"); + + return entry & (1 << mark_bit_bit_of(add)); +} + +BOOL background_object_marked(const DacpGcHeapDetails &heap, CLRDATA_ADDRESS o) +{ + BOOL m = TRUE; + + if ((o >= heap.background_saved_lowest_address) && (o < heap.background_saved_highest_address)) + m = mark_array_marked(heap, o); + + return m; +} + +BOOL fgc_should_consider_object(const DacpGcHeapDetails &heap, + CLRDATA_ADDRESS o, + const DacpHeapSegmentData &seg, + BOOL consider_bgc_mark_p, + BOOL check_current_sweep_p, + BOOL check_saved_sweep_p) +{ + // the logic for this function must be kept in sync with the analogous function in gc.cpp + BOOL no_bgc_mark_p = FALSE; + + if (consider_bgc_mark_p) + { + if (check_current_sweep_p && (o < heap.next_sweep_obj)) + { + no_bgc_mark_p = TRUE; + } + + if (!no_bgc_mark_p) + { + if(check_saved_sweep_p && (o >= heap.saved_sweep_ephemeral_start)) + { + no_bgc_mark_p = TRUE; + } + + if (!check_saved_sweep_p) + { + CLRDATA_ADDRESS background_allocated = seg.background_allocated; + if (o >= background_allocated) + { + no_bgc_mark_p = TRUE; + } + } + } + } + else + { + no_bgc_mark_p = TRUE; + } + + return no_bgc_mark_p ? TRUE : background_object_marked(heap, o); +} + +enum c_gc_state +{ + c_gc_state_marking, + c_gc_state_planning, + c_gc_state_free +}; + +inline BOOL in_range_for_segment(const DacpHeapSegmentData &seg, CLRDATA_ADDRESS addr) +{ + return (addr >= seg.mem) && (addr < seg.reserved); +} + +void should_check_bgc_mark(const DacpGcHeapDetails &heap, + const DacpHeapSegmentData &seg, + BOOL* consider_bgc_mark_p, + BOOL* check_current_sweep_p, + BOOL* check_saved_sweep_p) +{ + // the logic for this function must be kept in sync with the analogous function in gc.cpp + *consider_bgc_mark_p = FALSE; + *check_current_sweep_p = FALSE; + *check_saved_sweep_p = FALSE; + + if (heap.current_c_gc_state == c_gc_state_planning) + { + // We are doing the next_sweep_obj comparison here because we have yet to + // turn on the swept flag for the segment but in_range_for_segment will return + // FALSE if the address is the same as reserved. + if ((seg.flags & heap_segment_flags_swept) || (heap.next_sweep_obj == seg.reserved)) + { + // this seg was already swept. + } + else + { + *consider_bgc_mark_p = TRUE; + + if (seg.segmentAddr == heap.saved_sweep_ephemeral_seg) + { + *check_saved_sweep_p = TRUE; + } + + if (in_range_for_segment(seg, heap.next_sweep_obj)) + { + *check_current_sweep_p = TRUE; + } + } + } +} + +// TODO: FACTOR TOGETHER THE OBJECT MEMBER WALKING CODE FROM +// TODO: VerifyObjectMember(), GetListOfRefs(), HeapTraverser::PrintRefs() +BOOL VerifyObjectMember(const DacpGcHeapDetails &heap, DWORD_PTR objAddr) +{ + BOOL ret = TRUE; + BOOL bCheckCard = TRUE; + size_t size = 0; + { + DWORD_PTR dwAddrCard = objAddr; + while (dwAddrCard < objAddr + size) + { + if (CardIsSet(heap, dwAddrCard)) + { + bCheckCard = FALSE; + break; + } + dwAddrCard += card_size; + } + + if (bCheckCard) + { + dwAddrCard = objAddr + size - 2*sizeof(PVOID); + if (CardIsSet(heap, dwAddrCard)) + { + bCheckCard = FALSE; + } + } + } + + for (sos::RefIterator itr(TO_TADDR(objAddr)); itr; ++itr) + { + TADDR dwAddr1 = (DWORD_PTR)*itr; + if (dwAddr1) + { + TADDR dwChild = dwAddr1; + // Try something more efficient than IsObject here. Is the methodtable valid? + size_t s; + BOOL bPointers; + TADDR dwAddrMethTable; + if (FAILED(GetMTOfObject(dwAddr1, &dwAddrMethTable)) || + (GetSizeEfficient(dwAddr1, dwAddrMethTable, FALSE, s, bPointers) == FALSE)) + { + DMLOut("object %s: bad member %p at %p\n", DMLObject(objAddr), SOS_PTR(dwAddr1), SOS_PTR(itr.GetOffset())); + ret = FALSE; + } + + if (IsMTForFreeObj(dwAddrMethTable)) + { + DMLOut("object %s contains free object %p at %p\n", DMLObject(objAddr), + SOS_PTR(dwAddr1), SOS_PTR(objAddr+itr.GetOffset())); + ret = FALSE; + } + + // verify card table + if (bCheckCard && NeedCard(objAddr+itr.GetOffset(), dwAddr1)) + { + DMLOut("object %s:%s missing card_table entry for %p\n", + DMLObject(objAddr), (dwChild == dwAddr1) ? "" : " maybe", + SOS_PTR(objAddr+itr.GetOffset())); + ret = FALSE; + } + } + } + + return ret; +} + +// search for can_verify_deep in gc.cpp for examples of how these functions are used. +BOOL VerifyObject(const DacpGcHeapDetails &heap, const DacpHeapSegmentData &seg, DWORD_PTR objAddr, DWORD_PTR MTAddr, size_t objSize, + BOOL bVerifyMember) +{ + if (IsMTForFreeObj(MTAddr)) + { + return TRUE; + } + + if (objSize < min_obj_size) + { + DMLOut("object %s: size %d too small\n", DMLObject(objAddr), objSize); + return FALSE; + } + + // If we requested to verify the object's members, the GC may be in a state where that's not possible. + // Here we check to see if the object in question needs to have its members updated. If so, we turn off + // verification for the object. + if (bVerifyMember) + { + BOOL consider_bgc_mark = FALSE, check_current_sweep = FALSE, check_saved_sweep = FALSE; + should_check_bgc_mark(heap, seg, &consider_bgc_mark, &check_current_sweep, &check_saved_sweep); + bVerifyMember = fgc_should_consider_object(heap, objAddr, seg, consider_bgc_mark, check_current_sweep, check_saved_sweep); + } + + return bVerifyMember ? VerifyObjectMember(heap, objAddr) : TRUE; +} + + +BOOL FindSegment(const DacpGcHeapDetails &heap, DacpHeapSegmentData &seg, CLRDATA_ADDRESS addr) +{ + CLRDATA_ADDRESS dwAddrSeg = heap.generation_table[GetMaxGeneration()].start_segment; + + // Request the inital segment. + if (seg.Request(g_sos, dwAddrSeg, heap) != S_OK) + { + ExtOut("Error requesting heap segment %p.\n", SOS_PTR(dwAddrSeg)); + return FALSE; + } + + // Loop while the object is not in range of the segment. + while (addr < TO_TADDR(seg.mem) || + addr >= (dwAddrSeg == heap.ephemeral_heap_segment ? heap.alloc_allocated : TO_TADDR(seg.allocated))) + { + // get the next segment + dwAddrSeg = seg.next; + + // We reached the last segment without finding the object. + if (dwAddrSeg == NULL) + return FALSE; + + if (seg.Request(g_sos, dwAddrSeg, heap) != S_OK) + { + ExtOut("Error requesting heap segment %p.\n", SOS_PTR(dwAddrSeg)); + return FALSE; + } + } + + return TRUE; +} + +BOOL VerifyObject(const DacpGcHeapDetails &heap, DWORD_PTR objAddr, DWORD_PTR MTAddr, size_t objSize, BOOL bVerifyMember) +{ + // This is only used by the other VerifyObject function if bVerifyMember is true, + // so we only intialize it if we need it for verifying object members. + DacpHeapSegmentData seg; + + if (bVerifyMember) + { + // if we fail to find the segment, we cannot verify the object's members + bVerifyMember = FindSegment(heap, seg, objAddr); + } + + return VerifyObject(heap, seg, objAddr, MTAddr, objSize, bVerifyMember); +} + +//////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////// +typedef void (*TYPETREEVISIT)(size_t methodTable, size_t ID, LPVOID token); + +// TODO remove this. MethodTableCache already maps method tables to +// various information. We don't need TypeTree to do this too. +// Straightfoward to do, but low priority. +class TypeTree +{ +private: + size_t methodTable; + size_t ID; + TypeTree *pLeft; + TypeTree *pRight; + +public: + TypeTree(size_t MT) : methodTable(MT),ID(0),pLeft(NULL),pRight(NULL) { } + + BOOL isIn(size_t MT, size_t *pID) + { + TypeTree *pCur = this; + + while (pCur) + { + if (MT == pCur->methodTable) + { + if (pID) + *pID = pCur->ID; + return TRUE; + } + else if (MT < pCur->methodTable) + pCur = pCur->pLeft; + else + pCur = pCur->pRight; + } + + return FALSE; + } + + BOOL insert(size_t MT) + { + TypeTree *pCur = this; + + while (pCur) + { + if (MT == pCur->methodTable) + return TRUE; + else if ((MT < pCur->methodTable)) + { + if (pCur->pLeft) + pCur = pCur->pLeft; + else + break; + } + else if (pCur->pRight) + pCur = pCur->pRight; + else + break; + } + + // If we got here, we need to append at the current node. + TypeTree *pNewNode = new TypeTree(MT); + if (pNewNode == NULL) + return FALSE; + + if (MT < pCur->methodTable) + pCur->pLeft = pNewNode; + else + pCur->pRight = pNewNode; + + return TRUE; + } + + static void destroy(TypeTree *pStart) + { + TypeTree *pCur = pStart; + + if (pCur) + { + destroy(pCur->pLeft); + destroy(pCur->pRight); + delete [] pCur; + } + } + + static void visit_inorder(TypeTree *pStart, TYPETREEVISIT pFunc, LPVOID token) + { + TypeTree *pCur = pStart; + + if (pCur) + { + visit_inorder(pCur->pLeft, pFunc, token); + pFunc (pCur->methodTable, pCur->ID, token); + visit_inorder(pCur->pRight, pFunc, token); + } + } + + static void setTypeIDs(TypeTree *pStart, size_t *pCurID) + { + TypeTree *pCur = pStart; + + if (pCur) + { + setTypeIDs(pCur->pLeft, pCurID); + pCur->ID = *pCurID; + (*pCurID)++; + setTypeIDs(pCur->pRight, pCurID); + } + } + +}; + +/////////////////////////////////////////////////////////////////////////////// +// + +HeapTraverser::HeapTraverser(bool verify) +{ + m_format = 0; + m_file = NULL; + m_objVisited = 0; + m_pTypeTree = NULL; + m_curNID = 1; + m_verify = verify; +} + +HeapTraverser::~HeapTraverser() +{ + if (m_pTypeTree) { + TypeTree::destroy(m_pTypeTree); + m_pTypeTree = NULL; + } +} + +BOOL HeapTraverser::Initialize() +{ + if (!GCHeapsTraverse (HeapTraverser::GatherTypes, this, m_verify)) + { + ExtOut("Error during heap traverse\n"); + return FALSE; + } + + GCRootImpl::GetDependentHandleMap(mDependentHandleMap); + + size_t startID = 1; + TypeTree::setTypeIDs(m_pTypeTree, &startID); + + return TRUE; +} + +BOOL HeapTraverser::CreateReport (FILE *fp, int format) +{ + if (fp == NULL || (format!=FORMAT_XML && format != FORMAT_CLRPROFILER)) + { + return FALSE; + } + + m_file = fp; + m_format = format; + + PrintSection(TYPE_START,TRUE); + + PrintSection(TYPE_TYPES,TRUE); + TypeTree::visit_inorder(m_pTypeTree, HeapTraverser::PrintOutTree, this); + PrintSection(TYPE_TYPES,FALSE); + + ExtOut("tracing roots...\n"); + PrintSection(TYPE_ROOTS,TRUE); + PrintRootHead(); + + TraceHandles(); + FindGCRootOnStacks(); + + PrintRootTail(); + PrintSection(TYPE_ROOTS,FALSE); + + // now print type tree + PrintSection(TYPE_OBJECTS,TRUE); + ExtOut("\nWalking heap...\n"); + m_objVisited = 0; // for UI updates + GCHeapsTraverse (HeapTraverser::PrintHeap, this, FALSE); // Never verify on the second pass + PrintSection(TYPE_OBJECTS,FALSE); + + PrintSection(TYPE_START,FALSE); + + m_file = NULL; + return TRUE; +} + +void HeapTraverser::insert(size_t mTable) +{ + if (m_pTypeTree == NULL) + { + m_pTypeTree = new TypeTree(mTable); + if (m_pTypeTree == NULL) + { + ReportOOM(); + return; + } + } + else + { + m_pTypeTree->insert(mTable); + } +} + +size_t HeapTraverser::getID(size_t mTable) +{ + if (m_pTypeTree == NULL) + { + return 0; + } + // IDs start at 1, so we can return 0 if not found. + size_t ret; + if (m_pTypeTree->isIn(mTable,&ret)) + { + return ret; + } + + return 0; +} + +#ifndef FEATURE_PAL +void replace(std::wstring &str, const WCHAR *toReplace, const WCHAR *replaceWith) +{ + const size_t replaceLen = _wcslen(toReplace); + const size_t replaceWithLen = _wcslen(replaceWith); + + size_t i = str.find(toReplace); + while (i != std::wstring::npos) + { + str.replace(i, replaceLen, replaceWith); + i = str.find(toReplace, i + replaceWithLen); + } +} +#endif + +void HeapTraverser::PrintType(size_t ID,LPCWSTR name) +{ + if (m_format==FORMAT_XML) + { +#ifndef FEATURE_PAL + // Sanitize name based on XML spec. + std::wstring wname = name; + replace(wname, W("&"), W("&")); + replace(wname, W("\""), W(""")); + replace(wname, W("'"), W("'")); + replace(wname, W("<"), W("<")); + replace(wname, W(">"), W(">")); + name = wname.c_str(); +#endif + fprintf(m_file, + "<type id=\"%d\" name=\"%S\"/>\n", + ID, name); + } + else if (m_format==FORMAT_CLRPROFILER) + { + fprintf(m_file, + "t %d 0 %S\n", + ID,name); + } +} + +void HeapTraverser::PrintObjectHead(size_t objAddr,size_t typeID,size_t Size) +{ + if (m_format==FORMAT_XML) + { + fprintf(m_file, + "<object address=\"0x%p\" typeid=\"%d\" size=\"%d\">\n", + (PBYTE)objAddr,typeID, Size); + } + else if (m_format==FORMAT_CLRPROFILER) + { + fprintf(m_file, + "n %d 1 %d %d\n", + m_curNID,typeID,Size); + + fprintf(m_file, + "! 1 0x%p %d\n", + (PBYTE)objAddr,m_curNID); + + m_curNID++; + + fprintf(m_file, + "o 0x%p %d %d ", + (PBYTE)objAddr,typeID,Size); + } +} + +void HeapTraverser::PrintObjectMember(size_t memberValue, bool dependentHandle) +{ + if (m_format==FORMAT_XML) + { + fprintf(m_file, + " <member address=\"0x%p\"%s/>\n", + (PBYTE)memberValue, dependentHandle ? " dependentHandle=\"1\"" : ""); + } + else if (m_format==FORMAT_CLRPROFILER) + { + fprintf(m_file, + " 0x%p", + (PBYTE)memberValue); + } +} + +void HeapTraverser::PrintObjectTail() +{ + if (m_format==FORMAT_XML) + { + fprintf(m_file, + "</object>\n"); + } + else if (m_format==FORMAT_CLRPROFILER) + { + fprintf(m_file, + "\n"); + } +} + +void HeapTraverser::PrintRootHead() +{ + if (m_format==FORMAT_CLRPROFILER) + { + fprintf(m_file, + "r "); + } +} + +void HeapTraverser::PrintRoot(LPCWSTR kind,size_t Value) +{ + if (m_format==FORMAT_XML) + { + fprintf(m_file, + "<root kind=\"%S\" address=\"0x%p\"/>\n", + kind, + (PBYTE)Value); + } + else if (m_format==FORMAT_CLRPROFILER) + { + fprintf(m_file, + "0x%p ", + (PBYTE)Value); + } +} + +void HeapTraverser::PrintRootTail() +{ + if (m_format==FORMAT_CLRPROFILER) + { + fprintf(m_file, + "\n"); + } +} + +void HeapTraverser::PrintSection(int Type,BOOL bOpening) +{ + const char *const pTypes[] = {"<gcheap>","<types>","<roots>","<objects>"}; + const char *const pTypeEnds[] = {"</gcheap>","</types>","</roots>","</objects>"}; + + if (m_format==FORMAT_XML) + { + if ((Type >= 0) && (Type < TYPE_HIGHEST)) + { + fprintf(m_file,"%s\n",bOpening ? pTypes[Type] : pTypeEnds[Type]); + } + else + { + ExtOut ("INVALID TYPE %d\n", Type); + } + } + else if (m_format==FORMAT_CLRPROFILER) + { + if ((Type == TYPE_START) && !bOpening) // a final newline is needed + { + fprintf(m_file,"\n"); + } + } +} + +void HeapTraverser::FindGCRootOnStacks() +{ + ArrayHolder<DWORD_PTR> threadList = NULL; + int numThreads = 0; + + // GetThreadList calls ReportOOM so we don't need to do that here. + HRESULT hr = GetThreadList(&threadList, &numThreads); + if (FAILED(hr) || !threadList) + { + ExtOut("Failed to enumerate threads in the process.\n"); + return; + } + + int total = 0; + DacpThreadData vThread; + for (int i = 0; i < numThreads; i++) + { + if (FAILED(vThread.Request(g_sos, threadList[i]))) + continue; + + if (vThread.osThreadId) + { + unsigned int refCount = 0; + ArrayHolder<SOSStackRefData> refs = NULL; + + if (FAILED(::GetGCRefs(vThread.osThreadId, &refs, &refCount, NULL, NULL))) + { + ExtOut("Failed to walk thread %x\n", vThread.osThreadId); + continue; + } + + for (unsigned int i = 0; i < refCount; ++i) + if (refs[i].Object) + PrintRoot(W("stack"), TO_TADDR(refs[i].Object)); + } + } + +} + + +/* static */ void HeapTraverser::PrintOutTree(size_t methodTable, size_t ID, + LPVOID token) +{ + HeapTraverser *pHolder = (HeapTraverser *) token; + NameForMT_s(methodTable, g_mdName, mdNameLen); + pHolder->PrintType(ID,g_mdName); +} + + +/* static */ void HeapTraverser::PrintHeap(DWORD_PTR objAddr,size_t Size, + DWORD_PTR methodTable, LPVOID token) +{ + if (!IsMTForFreeObj (methodTable)) + { + HeapTraverser *pHolder = (HeapTraverser *) token; + pHolder->m_objVisited++; + size_t ID = pHolder->getID(methodTable); + + pHolder->PrintObjectHead(objAddr, ID, Size); + pHolder->PrintRefs(objAddr, methodTable, Size); + pHolder->PrintObjectTail(); + + if (pHolder->m_objVisited % 1024 == 0) { + ExtOut("."); + if (pHolder->m_objVisited % (1024*64) == 0) + ExtOut("\r\n"); + } + } +} + +void HeapTraverser::TraceHandles() +{ + unsigned int fetched = 0; + SOSHandleData data[64]; + + ToRelease<ISOSHandleEnum> handles; + HRESULT hr = g_sos->GetHandleEnum(&handles); + if (FAILED(hr)) + return; + + do + { + hr = handles->Next(_countof(data), data, &fetched); + + if (FAILED(hr)) + break; + + for (unsigned int i = 0; i < fetched; ++i) + PrintRoot(W("handle"), (size_t)data[i].Handle); + } while (fetched == _countof(data)); +} + +/* static */ void HeapTraverser::GatherTypes(DWORD_PTR objAddr,size_t Size, + DWORD_PTR methodTable, LPVOID token) +{ + if (!IsMTForFreeObj (methodTable)) + { + HeapTraverser *pHolder = (HeapTraverser *) token; + pHolder->insert(methodTable); + } +} + +void HeapTraverser::PrintRefs(size_t obj, size_t methodTable, size_t size) +{ + DWORD_PTR dwAddr = methodTable; + + // TODO: pass info to callback having to lookup the MethodTableInfo again + MethodTableInfo* info = g_special_mtCache.Lookup((DWORD_PTR)methodTable); + _ASSERTE(info->IsInitialized()); // This is the second pass, so we should be intialized + + if (!info->bContainsPointers) + return; + + // Fetch the GCInfo from the other process + CGCDesc *map = info->GCInfo; + if (map == NULL) + { + INT_PTR nEntries; + move_xp (nEntries, dwAddr-sizeof(PVOID)); + bool arrayOfVC = false; + if (nEntries<0) + { + arrayOfVC = true; + nEntries = -nEntries; + } + + size_t nSlots = 1+nEntries*sizeof(CGCDescSeries)/sizeof(DWORD_PTR); + info->GCInfoBuffer = new DWORD_PTR[nSlots]; + if (info->GCInfoBuffer == NULL) + { + ReportOOM(); + return; + } + + if (FAILED(rvCache->Read(TO_CDADDR(dwAddr - nSlots*sizeof(DWORD_PTR)), + info->GCInfoBuffer, (ULONG) (nSlots*sizeof(DWORD_PTR)), NULL))) + return; + + map = info->GCInfo = (CGCDesc*)(info->GCInfoBuffer+nSlots); + info->ArrayOfVC = arrayOfVC; + } + + mCache.EnsureRangeInCache((TADDR)obj, (unsigned int)size); + for (sos::RefIterator itr(obj, info->GCInfo, info->ArrayOfVC, &mCache); itr; ++itr) + { + if (*itr && (!m_verify || sos::IsObject(*itr))) + PrintObjectMember(*itr, false); + } + + std::unordered_map<TADDR, std::list<TADDR>>::iterator itr = mDependentHandleMap.find((TADDR)obj); + if (itr != mDependentHandleMap.end()) + { + for (std::list<TADDR>::iterator litr = itr->second.begin(); litr != itr->second.end(); ++litr) + { + PrintObjectMember(*litr, true); + } + } +} + + +void sos::ObjectIterator::BuildError(char *out, size_t count, const char *format, ...) const +{ + if (out == NULL || count == 0) + return; + + va_list args; + va_start(args, format); + + int written = vsprintf_s(out, count, format, args); + if (written > 0 && mLastObj) + sprintf_s(out+written, count-written, "\nLast good object: %p.\n", (int*)mLastObj); + + va_end(args); +} + +bool sos::ObjectIterator::VerifyObjectMembers(char *reason, size_t count) const +{ + if (!mCurrObj.HasPointers()) + return true; + + size_t size = mCurrObj.GetSize(); + size_t objAddr = (size_t)mCurrObj.GetAddress(); + TADDR mt = mCurrObj.GetMT(); + + INT_PTR nEntries; + MOVE(nEntries, mt-sizeof(PVOID)); + if (nEntries < 0) + nEntries = -nEntries; + + size_t nSlots = 1 + nEntries * sizeof(CGCDescSeries)/sizeof(DWORD_PTR); + ArrayHolder<DWORD_PTR> buffer = new DWORD_PTR[nSlots]; + + if (FAILED(g_ExtData->ReadVirtual(TO_CDADDR(mt - nSlots*sizeof(DWORD_PTR)), + buffer, (ULONG) (nSlots*sizeof(DWORD_PTR)), NULL))) + { + BuildError(reason, count, "Object %s has a bad GCDesc.", DMLObject(objAddr)); + return false; + } + + CGCDesc *map = (CGCDesc *)(buffer+nSlots); + CGCDescSeries* cur = map->GetHighestSeries(); + CGCDescSeries* last = map->GetLowestSeries(); + + const size_t bufferSize = sizeof(size_t)*128; + size_t objBuffer[bufferSize/sizeof(size_t)]; + size_t dwBeginAddr = (size_t)objAddr; + size_t bytesInBuffer = bufferSize; + if (size < bytesInBuffer) + bytesInBuffer = size; + + + if (FAILED(g_ExtData->ReadVirtual(TO_CDADDR(dwBeginAddr), objBuffer, (ULONG) bytesInBuffer,NULL))) + { + BuildError(reason, count, "Object %s: Failed to read members.", DMLObject(objAddr)); + return false; + } + + BOOL bCheckCard = TRUE; + { + DWORD_PTR dwAddrCard = (DWORD_PTR)objAddr; + while (dwAddrCard < objAddr + size) + { + if (CardIsSet (mHeaps[mCurrHeap], dwAddrCard)) + { + bCheckCard = FALSE; + break; + } + dwAddrCard += card_size; + } + if (bCheckCard) + { + dwAddrCard = objAddr + size - 2*sizeof(PVOID); + if (CardIsSet (mHeaps[mCurrHeap], dwAddrCard)) + { + bCheckCard = FALSE; + } + } + } + + if (cur >= last) + { + do + { + BYTE** parm = (BYTE**)((objAddr) + cur->GetSeriesOffset()); + BYTE** ppstop = + (BYTE**)((BYTE*)parm + cur->GetSeriesSize() + (size)); + while (parm < ppstop) + { + CheckInterrupt(); + size_t dwAddr1; + + // Do we run out of cache? + if ((size_t)parm >= dwBeginAddr+bytesInBuffer) + { + // dwBeginAddr += bytesInBuffer; + dwBeginAddr = (size_t)parm; + if (dwBeginAddr >= objAddr + size) + { + return true; + } + bytesInBuffer = bufferSize; + if (objAddr+size-dwBeginAddr < bytesInBuffer) + { + bytesInBuffer = objAddr+size-dwBeginAddr; + } + if (FAILED(g_ExtData->ReadVirtual(TO_CDADDR(dwBeginAddr), objBuffer, (ULONG) bytesInBuffer, NULL))) + { + BuildError(reason, count, "Object %s: Failed to read members.", DMLObject(objAddr)); + return false; + } + } + dwAddr1 = objBuffer[((size_t)parm-dwBeginAddr)/sizeof(size_t)]; + if (dwAddr1) { + DWORD_PTR dwChild = dwAddr1; + // Try something more efficient than IsObject here. Is the methodtable valid? + size_t s; + BOOL bPointers; + DWORD_PTR dwAddrMethTable; + if (FAILED(GetMTOfObject(dwAddr1, &dwAddrMethTable)) || + (GetSizeEfficient(dwAddr1, dwAddrMethTable, FALSE, s, bPointers) == FALSE)) + { + BuildError(reason, count, "object %s: bad member %p at %p", DMLObject(objAddr), + SOS_PTR(dwAddr1), SOS_PTR(objAddr+(size_t)parm-objAddr)); + + return false; + } + + if (IsMTForFreeObj(dwAddrMethTable)) + { + sos::Throw<HeapCorruption>("object %s contains free object %p at %p", DMLObject(objAddr), + SOS_PTR(dwAddr1), SOS_PTR(objAddr+(size_t)parm-objAddr)); + } + + // verify card table + if (bCheckCard && + NeedCard(objAddr+(size_t)parm-objAddr,dwChild)) + { + BuildError(reason, count, "Object %s: %s missing card_table entry for %p", + DMLObject(objAddr), (dwChild == dwAddr1)? "" : " maybe", + SOS_PTR(objAddr+(size_t)parm-objAddr)); + + return false; + } + } + parm++; + } + cur--; + CheckInterrupt(); + + } while (cur >= last); + } + else + { + int cnt = (int) map->GetNumSeries(); + BYTE** parm = (BYTE**)((objAddr) + cur->startoffset); + while ((BYTE*)parm < (BYTE*)((objAddr)+(size)-plug_skew)) + { + for (int __i = 0; __i > cnt; __i--) + { + CheckInterrupt(); + + unsigned skip = cur->val_serie[__i].skip; + unsigned nptrs = cur->val_serie[__i].nptrs; + BYTE** ppstop = parm + nptrs; + do + { + size_t dwAddr1; + // Do we run out of cache? + if ((size_t)parm >= dwBeginAddr+bytesInBuffer) + { + // dwBeginAddr += bytesInBuffer; + dwBeginAddr = (size_t)parm; + if (dwBeginAddr >= objAddr + size) + return true; + + bytesInBuffer = bufferSize; + if (objAddr+size-dwBeginAddr < bytesInBuffer) + bytesInBuffer = objAddr+size-dwBeginAddr; + + if (FAILED(g_ExtData->ReadVirtual(TO_CDADDR(dwBeginAddr), objBuffer, (ULONG) bytesInBuffer, NULL))) + { + BuildError(reason, count, "Object %s: Failed to read members.", DMLObject(objAddr)); + return false; + } + } + dwAddr1 = objBuffer[((size_t)parm-dwBeginAddr)/sizeof(size_t)]; + { + if (dwAddr1) + { + DWORD_PTR dwChild = dwAddr1; + // Try something more efficient than IsObject here. Is the methodtable valid? + size_t s; + BOOL bPointers; + DWORD_PTR dwAddrMethTable; + if (FAILED(GetMTOfObject(dwAddr1, &dwAddrMethTable)) || + (GetSizeEfficient(dwAddr1, dwAddrMethTable, FALSE, s, bPointers) == FALSE)) + { + BuildError(reason, count, "Object %s: Bad member %p at %p.\n", DMLObject(objAddr), + SOS_PTR(dwAddr1), SOS_PTR(objAddr+(size_t)parm-objAddr)); + + return false; + } + + if (IsMTForFreeObj(dwAddrMethTable)) + { + BuildError(reason, count, "Object %s contains free object %p at %p.", DMLObject(objAddr), + SOS_PTR(dwAddr1), SOS_PTR(objAddr+(size_t)parm-objAddr)); + return false; + } + + // verify card table + if (bCheckCard && + NeedCard (objAddr+(size_t)parm-objAddr,dwAddr1)) + { + BuildError(reason, count, "Object %s:%s missing card_table entry for %p", + DMLObject(objAddr), (dwChild == dwAddr1) ? "" : " maybe", + SOS_PTR(objAddr+(size_t)parm-objAddr)); + + return false; + } + } + } + parm++; + CheckInterrupt(); + } while (parm < ppstop); + parm = (BYTE**)((BYTE*)parm + skip); + } + } + } + + return true; +} + +bool sos::ObjectIterator::Verify(char *reason, size_t count) const +{ + try + { + TADDR mt = mCurrObj.GetMT(); + + if (MethodTable::GetFreeMT() == mt) + { + return true; + } + + size_t size = mCurrObj.GetSize(); + if (size < min_obj_size) + { + BuildError(reason, count, "Object %s: Size %d is too small.", DMLObject(mCurrObj.GetAddress()), size); + return false; + } + + if (mCurrObj.GetAddress() + mCurrObj.GetSize() > mSegmentEnd) + { + BuildError(reason, count, "Object %s is too large. End of segment at %p.", DMLObject(mCurrObj), mSegmentEnd); + return false; + } + + BOOL bVerifyMember = TRUE; + + // If we requested to verify the object's members, the GC may be in a state where that's not possible. + // Here we check to see if the object in question needs to have its members updated. If so, we turn off + // verification for the object. + BOOL consider_bgc_mark = FALSE, check_current_sweep = FALSE, check_saved_sweep = FALSE; + should_check_bgc_mark(mHeaps[mCurrHeap], mSegment, &consider_bgc_mark, &check_current_sweep, &check_saved_sweep); + bVerifyMember = fgc_should_consider_object(mHeaps[mCurrHeap], mCurrObj.GetAddress(), mSegment, + consider_bgc_mark, check_current_sweep, check_saved_sweep); + + if (bVerifyMember) + return VerifyObjectMembers(reason, count); + } + catch(const sos::Exception &e) + { + BuildError(reason, count, e.GetMesssage()); + return false; + } + + return true; +} + +bool sos::ObjectIterator::Verify() const +{ + char *c = NULL; + return Verify(c, 0); +} |