Быстрая трассировка стека захвата в Windows / 64-битном / смешанном режиме

Question

Как и многие из вас, наверное, знают, что существует множество различных механизмов для обхода трассировки стека, начиная с windows api и далее вглубь мира магической сборки - позвольте мне перечислить здесь некоторые ссылки, которые я уже изучил.

Для всего позвольте мне упомянуть, что я хочу иметь механизм анализа утечек памяти в смешанном режиме (управляемом и неуправляемом) / 64-битном + приложение AnyCPU и из всех окон. CaptureStackBackTrace для API наиболее подходит для моих нужд, но, как я уже проанализировал - он не поддерживает обход стека управляемого кода. Но этот API-интерфейс функции наиболее близок к тому, что мне нужно (поскольку он также вычисляет хэш обратной трассировки - уникальный идентификатор конкретного стека вызовов).

Я исключил разные подходы к обнаружению утечек памяти - большая часть программного обеспечения, которое я пробовал, либо дает сбой, либо работает ненадежно, либо дает плохие результаты.

Также я не хочу перекомпилировать существующее программное обеспечение и переопределять malloc / new другой механизм - потому что это тяжелая задача (у нас огромная база кода с большим количеством DLL). Также я подозреваю, что это не разовая работа, которую мне нужно выполнить - проблема возвращается с 1-2-летним циклом, в зависимости от того, кто и что кодировал, поэтому я бы предпочел иметь встроенную функцию обнаружения утечек памяти в самом приложении (память api hooking) вместо того, чтобы снова и снова бороться с этой проблемой.

http://www.codeproject.com/Articles/11132/Walking-the-callstack

Использует функцию Windows StackWalk64 API, но не работает с управляемым кодом. Также 64-битная поддержка мне не совсем понятна - я видел обходной путь для 64-битной проблемы - я подозреваю, что этот код не работает полностью, когда обход стека выполняется в том же потоке.

Тогда существует хакер процесса: http://processhacker.sourceforge.net/

Он также использует StackWalk64, но расширяет его функцию обратного вызова (7-й и 8-й параметры) для поддержки обхода стека в смешанном режиме. После многих сложностей с функциями обратного вызова 7/8 мне удалось также достичь поддержки StackWalk64 с поддержкой смешанного режима (отслеживание трассировки стека в виде вектора - где каждый указатель относится к месту сборки / dll, где проходил вызов). Но, как вы можете догадаться, производительность StackWalk64 недостаточна для моих нужд - даже при использовании простого окна сообщений со стороны C# приложение просто "зависает" на некоторое время, пока не запустится правильно.

Я не видел таких больших задержек с вызовом функции CaptureStackBackTrace, поэтому я предполагаю, что производительность StackWalk64 недостаточна для моих нужд.

Существует также основанный на COM подход определения трассировки стека, например: http://www.codeproject.com/Articles/371137/A-Mixed-Mode-Stackwalk-with-the-IDebugClient-Inter

http://blog.steveniemitz.com/building-a-mixed-mode-stack-walker-part-1/

но то, чего я боюсь - это требует COM, и поток должен быть инициализирован com, и из-за перехвата api памяти я не должен касаться состояния com внутри какого-либо потока, потому что это может привести к более тяжелым проблемам (например, неправильная инициализация квартиры, другое глюки)

Теперь я достиг точки, когда Windows API становится недостаточно для моих собственных нужд, и мне нужно пройтись по стеку вызовов вручную. Такие примеры можно найти, например:

http://www.codeproject.com/Articles/11221/Easy-Detection-of-Memory-Leaks См. только функцию FillStackInfo / 32-битная, не поддерживает управляемый код.

Есть несколько упоминаний об обращении трассировки стека - например, по следующим ссылкам:

1. http://blog.airesoft.co.uk/2009/02/grabbing-kernel-thread-contexts-the-process-explorer-way/
2. http://cbloomrants.blogspot.fi/2009/01/01-30-09-stack-tracing-on-windows.html
3. http://www.gamedev.net/topic/364861-stack-dump-on-win32-how-to-get-api-addresses/
4. http://eli.thegreenplace.net/2011/09/06/stack-frame-layout-on-x86-64/

Особенно 1, 3, 4 ссылки дают некоторые интересные ночные чтения.:-)

Но даже при этом они представляют собой довольно интересные механизмы, ни на одном из них нет полностью работающего демонстрационного примера.

Я предполагаю, что одним из примеров является реализация Wine dbghelp ("эмулятор" Windows для Linux), который также показывает, как именно StackWalk64 работает в конце, но я подозреваю, что он сильно привязан к исполняемому файлу формата DWARF2, поэтому он не идентичен текущей Windows PE формат исполняемого файла.

Может ли кто-нибудь подсказать мне хорошую реализацию стекового обхода, работающего на 64-битной архитектуре, с поддержкой смешанного режима (может отслеживать собственное и управляемое распределение памяти), который связан исключительно в анализе регистров / вызовов стека / кода. (Комбинированные реализации 1, 3, 4)

Есть ли у кого-нибудь хороший контакт из команды разработчиков Microsoft, который мог бы потенциально ответить на этот вопрос?

Answer 1

9-1-2015 - Я нашел оригинальную функцию, которая вызывается хакером процесса, и она была

C:\Windows\Microsoft.NET\Framework64\v4.0.30319\mscordacwks.dll OutOfProcessFunctionTableCallback

это исходный код - который был здесь: https://github.com/dotnet/coreclr/blob/master/src/debug/daccess/fntableaccess.cpp

Оттуда у меня есть владелец большинства изменений в этом исходном коде - Ян Котас ([e-mail]) и связался с ним по поводу этой проблемы.

From: Jan Kotas <[e-mail]>
To: Tarmo Pikaro <[e-mail]> 
Sent: Friday, January 8, 2016 3:27 PM
Subject: RE: Fast capture stack trace on windows 64 bit / mixed mode...

...

The mscordacwks.dll is called mscordaccore.dll in CoreCLR / github repro. The VS project 
files are auto-generated for it during the build 
(\coreclr\bin\obj\Windows_NT.x64.Debug\src\dlls\mscordac\mscordaccore.vcxproj).
You should be able to build and debug CoreCLR to understand how it works.
...

From: Jan Kotas <[e-mail]>
To: Tarmo Pikaro <[e-mail]> 
Sent: Saturday, January 9, 2016 2:02 AM
Subject: RE: Fast capture stack trace on windows 64 bit / mixed mode...

> I've tried to replace 
> C:\Windows\Microsoft.NET\Framework64\v4.0.30319\mscordacwks.dll dll loading 
> with C:\Prototyping\dotNet\coreclr-master\bin\obj\Windows_NT.x64.Debug\src\dlls\mscordac\Debug\mscordaccore.dll
> loading (just compiled), but if previously I could get mixed mode stack trace correctly:
> ...

mscordacwks.dll is tightly coupled with the runtime. You cannot mix and match them between runtimes.
What I meant is that you can use CoreCLR to understand how this works.

Но затем он порекомендовал это решение, которое работало на меня:

int CaptureStackBackTrace3(int FramesToSkip, int nFrames, PVOID* BackTrace, PDWORD pBackTraceHash)
{
    CONTEXT ContextRecord;
    RtlCaptureContext(&ContextRecord);

    UINT iFrame;
    for (iFrame = 0; iFrame < nFrames; iFrame++)
    {
        DWORD64 ImageBase;
        PRUNTIME_FUNCTION pFunctionEntry = RtlLookupFunctionEntry(ContextRecord.Rip, &ImageBase, NULL);

        if (pFunctionEntry == NULL)
            break;

        PVOID HandlerData;
        DWORD64 EstablisherFrame;
        RtlVirtualUnwind(UNW_FLAG_NHANDLER,
            ImageBase,
            ContextRecord.Rip,
            pFunctionEntry,
            &ContextRecord,
            &HandlerData,
            &EstablisherFrame,
            NULL);

        BackTrace[iFrame] = (PVOID)ContextRecord.Rip;
    }

    return iFrame;
}

В этом фрагменте кода по-прежнему отсутствует вычисление хеш-кода обратной трассировки, но это можно добавить позже.

Также очень важно отметить, что при отладке этого фрагмента кода следует использовать встроенную отладку, а не смешанный режим (в проекте C# по умолчанию используется смешанный режим), поскольку это каким-то образом нарушает трассировку стека в отладчике. (Что-то, чтобы выяснить, как и почему происходит такое искажение)

Есть еще один недостающий кусочек головоломки - как сделать разрешение символов полностью устойчивым к утилизации кода FreeLibrary / Jit, но это то, что мне еще нужно выяснить.

Обратите внимание, что RtlVirtualUnwind, скорее всего, будет работать только на 64-битной архитектуре, а не на ручной или 32-битной.

Еще одна забавная вещь заключается в том, что существует функция RtlCaptureStackBackTrace, которая чем-то напоминает функцию api windows CaptureStackBackTrace - но они как-то отличаются - по крайней мере, по именованию. Также, если вы проверяете RtlCaptureStackBackTrace - в конечном итоге он вызывает RtlVirtualUnwind - вы можете проверить это из исходных кодов ядра Windows Research.

RtlCaptureStackBackTrace
>
RtlWalkFrameChain
>
RtlpWalkFrameChain
>
RtlVirtualUnwind

Но то, что я проверил RtlCaptureStackBackTrace, не работает правильно. В отличие от функции RtlVirtualUnwind выше.

Это своего рода магия.:-)

Я продолжу эту анкету с вопросом фазы 2 - здесь:

Разрешить управляемую и собственную трассировку стека - какой API использовать?

Answer 2

Просто заметки для себя:

Очевидно, что CaptureStackBackTrace, вероятно, вызывает прямо или косвенно RtlCaptureStackBackTrace, и исходный код этой функции, по-видимому, в настоящее время является открытым исходным кодом - его можно искать с помощью "ядра исследования Windows".

Код, который я случайно нашел, собрав https://github.com/dotnet/coreclr/blob/master/src/unwinder/amd64/unwinder_amd64.cpp

где была ссылка в коде, заимствованном из ядра Windows:

Все ниже заимствовано из файла minkernel\ntos\rtl\amd64\exdsptch.c из Windows

и, погуглив немного больше, я обнаружил само ядро ​​Windows.

Может быть, я могу обновить эту функцию для поддержки управляемого стека (используя информацию от хакера процесса).

[4.1.2015] При более глубоком анализе создается впечатление, что основным узким местом производительности является не сам CaptureStackBackTrace - потому что это простая итерация, поиск структуры, а также обход стека в управляемом режиме, где я называю C:\Windows\Microsoft.NET\Framework64\v4.0.30319\mscordacwks.dll / OutOfProcessFunctionTableCallback - вы можете найти его исходный код в дистрибутиве.net и, очевидно, выделить его память для анализа скомпилированных структур JIT. Но проблема в том, что JIT-компиляция может изменяться всякий раз, и единственный способ получить надежную трассировку стека состоит в том, чтобы повторно запрашивать одну и ту же информацию снова и снова, что может привести к дополнительным расходам при распределении памяти. Я предполагаю, что код необходимо изменить так, чтобы аналогичный код mscordacwks не выделял память сам по себе, а использовал структуры времени выполнения для определения стека вызовов и записей таблицы функций / функций.

PS Если вы проголосуете за этот ответ, я хотел бы знать причину, почему, какова альтернатива. И лучше, если вы попробовали альтернативу самостоятельно.

Answer 3

x64 Ходьба в стеке сложна, как вы уже узнали. Простая альтернатива состоит в том, чтобы просто не делать этого, а оставлять трудные вещи для стекалистов ОС ETW. Это работает, и это намного быстрее, чем вы когда-либо получите.

Вы можете воспользоваться этим, выпустив свое собственное событие ETW. Перед этим вам нужно запустить сеанс ETW для вашего провайдера событий и включить обход стека для вашего провайдера. В Windows 7 есть ловушка, которая не работает, если все кадры управляемого стека не являются NGenned, потому что x64 ETW Stackwalker остановится, если он найдет кадр стека, который не находится ни в одном загруженном модуле, что верно для кода JITed.

Начиная с Windows 8, ETW Stackwalker будет всегда обходить первый МБ стека для стековых фреймов, что решает проблему JIT. JIT-компилятор генерирует Unwind Infos для сгенерированного кода, если включена трассировка ETW, и регистрирует его через RtlAddGrowableFunctionTable, что позволяет в первую очередь быстро проходить по стеку из ядра. Все работает иначе, когда трассировка ETW не включена из соображений совместимости.

Если вы ищете после утечки памяти malloc / free new / delete, вы также можете использовать функции bultin ОС для трассировки выделения кучи, которая уже существует с Windows 7. См. Запуск xperf -help и https://randomascii.wordpress.com/2015/04/27/etw-heap-tracingevery-allocation-recorded/ для получения дополнительной информации о трассировке распределения кучи. Вы можете включить его для уже запущенного процесса без проблем. Недостатком является то, что для любого реального приложения генерируемые данные огромны. Но если вам нужны только большие выделения, то это может помочь отслеживать только вызовы VirtualAlloc, которые также могут быть включены с минимальными издержками.

Управляемый код, начиная с.NET 4.5, также имеет своего собственного провайдера трассировки распределения ETW с обходом полного стека даже в 64-разрядной Windows 7, поскольку он сам выполняет полный управляемый стек. Дополнительную информацию можно найти в источниках CoreClr по адресу: ETW::SamplingLog::SendStackTrace в https://github.com/dotnet/coreclr/blob/master/src/inc/eventtracebase.h для получения более подробной информации.

Это только грубая схема того, что возможно. Чтобы действительно получить все необходимые детали, я боюсь, что понадобится целая книга. И я все еще изучаю новые вещи каждый день.

Вот сценарий heapalloc.cmd, который вы можете использовать для отслеживания распределения кучи. По умолчанию он записывает в кольцевой буфер размером 500 МБ, если утечка накапливается в течение более длительных периодов времени, и запись всех стеков распределения без их сжатия во время выполнения не будет работать с WPA. Но вы можете опубликовать процесс обработки огромного файла ETL и написать для него собственную программу просмотра.

@echo off 
setlocal enabledelayedexpansion
REM consider using a different drive for ETL output to prevent slowing down 
REM your application and to prevent lost buffers
set OUTDIR=C:\TEMP
set OUTFILENAME=HeapTracing.etl
REM Final output file
set OUTFILE=!OUTDIR!\!OUTFILENAME!
set CLRUNDOWNFILE=!OUTDIR!\clr_HeapDCend.etl
set KERNELFILE=!OUTDIR!\kernel.etl
set CLRSESSIONFILE=!OUTDIR!\clrHeapSession.etl
set HEAPUSERFILE=!OUTDIR!\HeapUserSession.etl
REM Default is allocation and realloc to track memory leaks
REM HeapFree is the other option to track double free calls
set HEAPTRACINGFLAGS=HeapAlloc+HeapRealloc 

if "%3" NEQ "" (
echo Overriding Heap Tracing Flags with: %3
set HEAPTRACINGFLAGS=%3
)


if "%1" EQU "-start" ( 
    call :StartTracing -PidNewProcess %2
    goto :Exit 
) 

if "%1" EQU "-attachPid" ( 
    call :StartTracing -Pids %2
    goto :Exit 
) 

if "%1" EQU "-startNext" (
    reg add "HKLM\Software\Microsoft\Windows NT\CurrentVersion\Image File Execution Options\%~nx2" /v TracingFlags /t REG_DWORD /d 1 /f
    if not %errorlevel% == 0 goto failure
    call :StartTracing -Pids 0
    goto :Exit
)

if "%1" EQU "-stop" ( 
    set XPERF_CreateNGenPdbs=1
    xperf -start ClrRundownSession -on e13c0d23-ccbc-4e12-931b-d9cc2eee27e4:0x118:5+a669021c-c450-4609-a035-5af59af4df18:0x118:5 -f "!CLRUNDOWNFILE!" -buffersize 256 -minbuffers 256 -maxbuffers 512 
    call :WaitUntilRundownCompleted "!CLRUNDOWNFILE!"
    xperf -stop -stop ClrSession ClrRundownSession HeapSession | findstr /V identifiable 2> NUL

    echo Merging profiles
    REM Reset symbol path to create the pdbs files in the output directory with in the directory with the same name like our etl file
    set TMPSYMBOLPATH=!_NT_SYMBOL_PATH!
    REM Each tool is using a different pdb cache folder. If you are using them side by side 
    REM you have to wait a long time to refresh the pdb cache. To spare the waiting time we use 
    REM the pdb cache folder from WPR

    mkdir C:\ProgramData\WindowsPerformanceRecorder\NGenPdbs_Cache 2> NUL
    set _NT_SYMBOL_PATH=srv*C:\ProgramData\WindowsPerformanceRecorder\NGenPdbs_Cache 
    mklink /D "!OUTFILE!.NGENPDB" C:\ProgramData\WindowsPerformanceRecorder\NGenPdbs_Cache  2> NUL

    echo Managed PDBs are stored at: !OUTFILE!.NGENPDB. If you want to transfer the etl do not forget to copy this directory with the pdbs as well. 
    echo Merging ETL files and generating native pdbs

    xperf -merge  "!KERNELFILE!" "!CLRSESSIONFILE!" "!CLRUNDOWNFILE!" "!HEAPUSERFILE!" "!OUTFILE!"
    set _NT_SYMBOL_PATH=!TMPSYMBOLPATH!
    echo !OUTFILE! was created

    if "%2" NEQ "" reg delete "HKLM\Software\Microsoft\Windows NT\CurrentVersion\Image File Execution Options\%~nx2" /v TracingFlags /f 2> NUL
    goto :Exit 
) 

goto Usage:

:StartTracing
xperf -start ClrSession -on  Microsoft-Windows-DotNETRuntime:5 -f "!CLRSESSIONFILE!" -buffersize 128 -minbuffers 256 -maxbuffers 512 
xperf -on PROC_THREAD+LOADER+latency+virt_alloc -stackwalk VirtualAlloc  -f "%KERNELFILE%"
xperf -start HeapSession -heap %1 %2 -BufferSize 1024 -MinBuffers 128 -MaxBuffers 1024 -stackwalk %HEAPTRACINGFLAGS% -f "!HEAPUSERFILE!" -FileMode Circular -MaxFile 1024
exit /B

REM Wait until writing to ETL file has stopped by checking its file size
:WaitUntilRundownCompleted
:StillWriting
    for %%F in (%1) do set "size=%%~zF"
    timeout /T 1  > nul
    for %%F in (%1) do set "size2=%%~zF"
    if "!size!" EQU "" goto :EndWriting
    if "!size!" NEQ "!size2!" goto StillWriting
:EndWriting
timeout /T 1  > nul
exit /B


:Usage
    echo Usage: 
    echo HeapAlloc.cmd -start [executable] or -stop
    echo               -start [executable] Start a trace session 
    echo               -startNext [executable] Start heap tracing for all subsequent calls to executable.
    echo               -attachPid ddd Start a trace session for specified process
    echo               -stop  [executable] Stop a trace session 
    echo Examples
    echo     HeapAlloc.cmd -startNext devenv.exe
    echo     HeapAlloc.cmd -stop      devenv.exe
    echo To attach to a running process
    echo     HeapAlloc.cmd -attachPid dddd
    echo     HeapAlloc.cmd -stop 
    echo You must call -stop for your executable if you have used -start or startNext because heap allocation tracing will enabled until you stop it!
goto :Exit 

:failure
    echo Error occured
goto :Exit

:Exit

Answer 4

25.1.2016 Написание как отдельный вопрос, как дополнительная информация.

Для уникального идентификатора стека CaptureStackBackTrace использует простую сумму всех указателей инструкций - идея заимствована из: "Windows_Research_Kernel(sources)\WRK-v1.2\base\ntos\rtl\amd64\stkwalk.c":

    size_t hashValue = 0;

    for (int i = 0; i < nFrames; i++)
        hashValue += PtrToUlong(BackTrace[i]);

    *pBackTraceHash = (DWORD)hashValue;

Я не уверен насчет последнего преобразования - некоторые указывают последний параметр как DWORD, некоторые как ulong64, но это не имеет значения. Основная проблема этого расчета в том, что он не достаточно уникален. В случае рекурсивных вызовов функций - если у вас есть порядок вызовов:

func1
func2
func3

Трассировка стека для:

func1
func3
func2

Будет идентичным

Что я отлаживал - для обнаружения утечки памяти я получаю 62876 ложных попаданий - уникальный идентификатор стека недостаточно надежен.

Я немного переключил формулу:

static DWORD crc32_tab[] =
{
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
    0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
    0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};

if (pBackTraceHash)
{

    size_t hashValue = 0;
    for( int idxFrame = 0; idxFrame < (int)iFrame; idxFrame++ )
    {
        unsigned char* p = (unsigned char*)&BackTrace[idxFrame];
        for( int i = 0; i < sizeof(void*); i++ )
            hashValue = crc32_tab[ ((hashValue ^ *p++) & 0xFF) ] ^ (hashValue >> 8);
    }
    *pBackTraceHash = (DWORD)hashValue;
}

Этот алгоритм не дает ложных попаданий, но немного замедляет выполнение.

Отличается также статистика утечек памяти: Ненадежный алгоритм: общий объем утечки памяти: 48'874'764 / в 371 пуле выделения. Алгоритм на основе Crc32: общий объем утечки памяти: 48'874'764 / в 614 пулах выделения.

Как вы видите - статистика объединяет (объединяет) одинаковый стек вызовов вместе - меньше фрагментации, но оригинальный стек вызовов теряется. (Неверная статистика)

Может быть, кто-нибудь может дать мне более быстрый алгоритм для этого?

Answer 5

27.1.2016 А может быть и речи не идет - это определение 32-битного стека вызовов. Я спросил о том, какой API использовать - по крайней мере CaptureStackBackTrace производит неполные обходы (только собственный код), а также функция API RtlVirtualUnwind не существует для 32-битных окон.

From: Noah Falk <[e-mail]>
To: Tarmo Pikaro <[e-mail]>; Mike McLaughlin <[e-mail]> 
Cc: Jan Kotas <[e-mail]>
Sent: Tuesday, January 26, 2016 1:34 AM
Subject: RE: Resolving managed call stack from void*

Hi Tarmo, hope the exploration of stackwalking has been interesting. 
If I followed you correctly you’ve been successful on x64 but hoping you can extend your technique to 32 bit. 
Indeed the RtlCaptureVirtualUnwind techniques don’t work here, and the fundamental reason behind it is that 
while x64 defines a specific calling convention that all code on Windows is forced to use, x86 does not. 
This means that there is no algorithm the OS could implement which guarantees correct unwinding when PDBs are 
unavailable. However you do have some options:

1)      You can use simple heuristics that work for certain kinds of code. 
Unoptimzed code on x86 often uses EBP chaining, in which ESP in the current frame points to EBP, and EBP points 
to the parent frame’s EBP, and so on down the stack. The return address is stored on the stack adjacent to EBP. 
As I recall all jitted code produced by recent versions of .Net follows these conventions, including optimized 
jitted code. However when a compiler performs inlining these conventions will be unable to detect it, and optimized 
code that does not follow this convention could easily cause the stack to become unwalkable.

2)      If you are willing to load PDBs you can use the DIA APIs to walk the stack: 
https://msdn.microsoft.com/en-us/library/dt06fh94.aspx. The PDB contains additional data about optimized code 
which allows frames that do not follow the EBP chaining convention to be correctly unwound. 
This is the stack walk API that Visual Studio is using when it debugs 32 bit native code on Windows.

3)      The ICorDebug APIs (https://msdn.microsoft.com/en-us/library/dd646502(v=vs.110).aspx) are a set of 
APIs that are designed to support managed code debuggers. Starting in .Net 4.0 the ICorDebug API supports 
dump debugging, however the API is designed in such a way that you don’t have to serialize a dump file. 
This is likely to be more complicated than you would want, but its supported to the use the Windows process 
snapshot APIs to take a snapshot of the memory space and then direct the ICorDebug API to read from this 
snapshot as if it was a dump. One advantage of the ICorDebug API is that not only will it give you managed 
stack frames, it also allows exporing all the other kinds of data debuggers would expose such as parameters, 
local values, fields of objects, types of the values, etc.

The MDbg tool (https://www.microsoft.com/en-us/download/details.aspx?id=2282) is a complete sample debugger 
with source included. It supports dump debugging and displaying callstacks, though it won’t have any specific 
example about using the process snapshot APIs in place of using a dump. The main change would be replacing 
the implementation of ICorDebugDataTarget. MDbg has an implementation that reads from a dump file and you 
would need to create a new implementation that reads from a process snapshot using the windows APIs 
(https://msdn.microsoft.com/en-us/library/dn457825(v=vs.85).aspx). I’ve never written the code myself and 
I’ve heard from other tool authors that they found using the windows snapshot APIs more difficult than expected,
 but eventually they were successful.

И я был немного вдохновлен подходом 1, так как уже видел подобный подход в другом проекте, поэтому я написал свою собственную реализацию для обхода 32-битного стека:

int CaptureStackBackTracePro( int FramesToSkip, int nFrames, PVOID* BackTrace, PDWORD pBackTraceHash )
{
    //
    //  This approach was taken from StackInfoManager.cpp / FillStackInfo
    //  http://www.codeproject.com/Articles/11221/Easy-Detection-of-Memory-Leaks
    //  - slightly simplified the function itself.
    //
    int regEBP;
    __asm mov regEBP, ebp;

    long *pFrame = (long*) regEBP;              // pointer to current function frame
    void* pNextInstruction;
    int iFrame = 0;

    //
    // Using __try/_catch is faster than using ReadProcessMemory or VirtualProtect.
    // We return whatever frames we have collected so far after exception was encountered.
    //
    __try {
        for( ; iFrame < nFrames; iFrame++ )
        {
            pNextInstruction = (void*)(*(pFrame + 1));

            if( !pNextInstruction )     // Last frame
                break;

            BackTrace[iFrame] = pNextInstruction;
            pFrame = (long*)(*pFrame);
        }
    }
    __except(EXCEPTION_EXECUTE_HANDLER) 
    {
    }

    // pBackTraceHash fillout is missing, see in another answer code snipet.

    return iFrame;

} //CaptureStackBackTracePro

Краткие тесты показывают, что эта функция может захватывать собственные и управляемые кадры стека.

Я думаю, что оптимизированный код требует более глубокого анализа. Лучше не использовать оптимизацию или оптимизировать только соответствующие части кода - для лучшей диагностики?!

Answer 6

Кстати, если кому-то не хватает оригинальной реализации StackWalk для Windows, она находится здесь:

https://github.com/dotnet/coreclr/blob/master/src/utilcode/stacktrace.cpp