[Win32] [Asm] Race condition between bit fields #2

前回の記事の続きです。

[Win32] [Asm] Race condition between bit fields | すなのかたまり
https://msmania.wordpress.com/2013/11/30/win32-asm-race-condition-between-bit-fields/

ビットフィールドに値をセットするコードで、x86 と x64 のコンパイル結果が微妙に異なっていました。そして、x86 ではメモリに対して直接 xor しているのに対し、x64 では、xor した結果をレジスタに保存してから、それをメモリに mov するという方法を取っていました。つまり x64 の処理では、セットしたいビット以外のビットも mov によって上書きされてしまう可能性があるということです。しかし実際には、アセンブラ上は競合しないように見える x86 も競合が発生し、CPU キャッシュを原因の一つとして考えています。

CPU キャッシュの話はさておいて、何とかして x64 のコンパイル結果を咎める検証を行いたいものです。理論的には、シングル プロセッサーの環境であっても、コンテキスト スイッチの発生するタイミングによっては競合が発生するはずです。

アセンブラを再掲します。

x64 (競合するはず)

win32c!ChurningThread+0x90:
00007ff7`50b11090 0fb70555250000  movzx   eax,word ptr [win32c!g_Target+0x4 (00007ff7`50b135ec)]
00007ff7`50b11097 0fb70d861f0000  movzx   ecx,word ptr [win32c!g_FlipFlop (00007ff7`50b13024)]
00007ff7`50b1109e 6603c9          add     cx,cx
00007ff7`50b110a1 6633c8          xor     cx,ax
00007ff7`50b110a4 6683e102        and     cx,2
00007ff7`50b110a8 6633c1          xor     ax,cx

00007ff7`50b110ab 6689053a250000  mov     word ptr [win32c!g_Target+0x4 (00007ff7`50b135ec)],ax

win32c!ChurningThread+0xfc:
00007ff7`50b110fc 0fb705e9240000  movzx   eax,word ptr [win32c!g_Target+0x4 (00007ff7`50b135ec)]
00007ff7`50b11103 0fb70d1a1f0000  movzx   ecx,word ptr [win32c!g_FlipFlop (00007ff7`50b13024)]
00007ff7`50b1110a 6633c8          xor     cx,ax
00007ff7`50b1110d 6683e101        and     cx,1
00007ff7`50b11111 6633c1          xor     ax,cx

00007ff7`50b11114 668905d1240000  mov     word ptr [win32c!g_Target+0x4 (00007ff7`50b135ec)],ax

x86 (競合は発生しないはず)

00bd1060 8b0d8433bd00    mov     ecx,dword ptr [win32c!g_Target+0x4 (00bd3384)]

win32c!ChurningThread+0x69:
00bd1069 a12030bd00      mov     eax,dword ptr [win32c!g_FlipFlop (00bd3020)]
00bd106e 03c0            add     eax,eax
00bd1070 33c1            xor     eax,ecx
00bd1072 83e002          and     eax,2
00bd1075 6631058433bd00  xor     word ptr [win32c!g_Target+0x4 (00bd3384)],ax

00bd10b5 8b0d8433bd00    mov     ecx,dword ptr [win32c!g_Target+0x4 (00bd3384)]

win32c!ChurningThread+0xbe:
00bd10be a12030bd00      mov     eax,dword ptr [win32c!g_FlipFlop (00bd3020)]
00bd10c3 33c1            xor     eax,ecx
00bd10c5 83e001          and     eax,1
00bd10c8 6631058433bd00  xor     word ptr [win32c!g_Target+0x4 (00bd3384)],ax

コンパイル結果がおかしいといえど、コンテキスト スイッチが発生すると困る (検証のためにはもちろん発生して欲しい) 箇所はかなり狭く、上の紫で示した 4 または 5 命令の部分です。この数クロックのタイミングでコンテキスト スイッチが発生するまでプログラムを動かし続けるのは現実的ではありません。そこで一般的な方法は、コンテキスト スイッチを発生させたいところが遅くなるようにコードを書き換えることです。といっても、C 言語だとビットフィールドへの代入という 1 行で済んでしまうコードなので、途中に Sleep を入れるわけにはいきません。インライン アセンブラを使いたいところですが、残念ながら x64 ではインライン アセンブラも使えません。デバッガーでコード領域をがりがり書き換える方法もありますが、今回は勉強もかねて MASM でアセンブラを書いてみることにしました。

書いたコードを以下に示します。x64 と x86 の両方を実装しており、x64 用の関数は 4 つです。

  • SetBit0 – 最上位ビットに値をセット (コンパイラに忠実なコード)
  • SetBit1 – 2 つ目ののビットに値をセット (コンパイラに忠実なコード)
  • SetBit0Safe – 最上位ビットに値をセット (メモリに直接 xor する安全なコード)
  • SetBit1Safe – 2 つ目のビットに値をセット (メモリに直接 xor する安全なコード)

まずは setbit.asm。パラメーターを明記せずにいきなり rcx や rdx を弄っているのでとっても危険です。

;
; setbit.asm
;
;
http://msdn.microsoft.com/en-us/library/vstudio/ss9fh0d6.aspx
;

ifndef X64

.model flat, C

endif

.data
; something

.code

ifdef X64

SetBit0 proc
  mov r8d, [rcx]
  xor dx, r8w
  and dx, 1
  xor r8w, dx
  INCLUDE nop50.asm
  mov [rcx], r8w
  ret
SetBit0 endp

SetBit1 proc
  mov r8d, [rcx]
  add dx, dx
  xor dx, r8w
  and dx, 2
  xor r8w, dx
  mov [rcx], r8w
  ret
SetBit1 endp

SetBit0Safe proc
  mov r8w, [rcx]
  xor r8w, dx
  and r8w, 1
  INCLUDE nop50.asm
  xor [rcx], r8w
  ret
SetBit0Safe endp

SetBit1Safe proc
  mov r8w, [rcx]
  shl dx, 1
  xor r8w, dx
  and r8w, 2
  xor [rcx], r8w
  ret
SetBit1Safe endp

else

SetBit0 proc var1:DWORD, var2:DWORD
  mov eax, [var1]
  mov ecx, [eax]
  mov eax, [var2]
  xor eax, ecx
  and eax, 1
  INCLUDE nop50.asm
  mov ecx, [var1]
  xor word ptr [ecx], ax
  ret
SetBit0 endp

SetBit1 proc var1:DWORD, var2:DWORD
  mov eax, [var1]
  mov ecx, [eax]
  mov eax, [var2]
  add eax, eax
  xor eax, ecx
  and eax, 2
  mov ecx, [var1]
  xor word ptr [ecx], ax
  ret
SetBit1 endp

endif

END

INCLUDE nop50.asm という箇所がありますが、nop50.asm は nop を 50 行書いているだけです。これで、コンテキスト スイッチを誘う処理の遅延を発生させます。Bit0 の関数だけに入れました。この nop を実行している間に、別スレッド経由でg_FlipFlop の反転が発生すればよいわけです。

nop50.asm の内容。

nop
nop
nop
(中略。50 行 nop が続きます。)
nop
nop
nop
nop

MASM のアセンブラーは Visual Studio 2012 に含まれていて、手元の環境では以下の場所にありました。Microsoft Macro Assembler (MASM) というものです。

C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\bin\amd64\ml64.exe
C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\bin\ml.exe

なお、ARM のアセンブラーは以下の場所にありました。MASM とは呼ばれないようです。

C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\bin\x86_arm\armasm.exe

ARM Assembler Command-Line Reference
http://msdn.microsoft.com/en-us/library/vstudio/hh873189.aspx

上手いことやれば MASM を Visual Studio のプロジェクトに完全に統合できそうですが、調べるのが面倒だったので、アセンブルするバッチ ファイルを書いて、Pre-Build Event から呼び出すという方法を取りました。これも相当に面倒でしたが。

書いたバッチ ファイルはこちら。goasm.bat です。第一引数で x86 と x64 を区別させます。

SET ML64=C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\bin\amd64\ml64.exe
SET ML32=C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\bin\ml.exe

IF /I "%1"=="X86" (
"%ml32%" /nologo /Fo asm\setbit32.obj /c /safeseh /Zi asm\setbit.asm
)

IF /I "%1"=="X64" (
"%ml64%" /nologo /Fo asm\setbit64.obj /c /Zi /DX64 asm\setbit.asm
)

次に Visual Studio 側でごにょごにょ設定します。うーん、GUI めんどくさい・・・。

image すべての環境で goasm.bat を実行

image Win32 では setbit32.obj をリンク

image x64 では setbit64.obj をリンク

さて、あとはソースコードをちょっと修正するだけです。

  • ビットの代入の代わりに SetBit0/SetBit1 を使用
  • 共用体を追加
  • 一つのプロセッサー上で動かすため、各スレッドに対して SetThreadAffinityMask API を実行
  • とにかく回数をこなさないといけないので、ループ内の Sleep を削除

こんな感じになりました。

//
// bitfield.cpp
//

#include <windows.h>
#include <stdio.h>

#define NTDLL_DLL L"ntdll.dll"

#define BETWEEN(n, a, b) ((n)>=(a) && (n)<=(b))
#define LOGERROR(fmt, …) wprintf(fmt, __VA_ARGS__)
#define LOGINFO LOGERROR
#define LOGDEBUG

extern "C" void SetBit0(PWORD, BOOL);
extern "C" void SetBit1(PWORD, BOOL);

#ifdef _WIN64
extern "C" void SetBit0Safe(PWORD, BOOL);
extern "C" void SetBit1Safe(PWORD, BOOL);
#else
#define SetBit0Safe SetBit0
#define SetBit1Safe SetBit1
#endif

typedef ULONG (WINAPI *RTLRANDOM)(
  _Inout_  PULONG Seed
);

HMODULE NtDllDll = NULL;
RTLRANDOM RtlRandom = NULL;

BOOL g_FlipFlop = TRUE;
BOOL g_Field1 = TRUE;
BOOL g_Field2 = TRUE;

struct TARGET {
    INT Int1;
    union {
        struct {
            WORD Field1:1;
            WORD Field2:1;
        };
        WORD Word;
    };
    INT Int2;
} g_Target;

typedef struct _CONTEXT_CHURN {
    ULONG   DynamicSeed;
    INT     Iteration;
    INT     ThreadIndex;
    INT     LoopCounter;
} CONTEXT_CHURN, *PCONTEXT_CHURN;

DWORD WINAPI ChurningThread(
  _In_  LPVOID lpParameter
) {
    PCONTEXT_CHURN Context = (PCONTEXT_CHURN)lpParameter;
   
    for ( int i=0 ; i<Context->Iteration ; ++i, ++Context->LoopCounter ) {
        switch (Context->ThreadIndex)
        {
        case 0:
            g_FlipFlop = !g_FlipFlop;
            break;
        case 1:
            if ( g_Target.Field1!=g_Field1 ) {
                LOGINFO(L"[ChurningThread.%04x] %d: g_Target.Field1=%d g_Field1=%d \n",
                    GetCurrentThreadId(),
                    Context->LoopCounter,
                    g_Target.Field1, g_Field1);
            }
            //g_Target.Field1 = g_FlipFlop;
            SetBit0(&g_Target.Word, g_FlipFlop);
            g_Field1 = g_Target.Field1;
            break;
        case 2:
            if ( g_Target.Field2!=g_Field2) {
                LOGINFO(L"[ChurningThread.%04x] %d: g_Target.Field2=%d g_Field2=%d \n",
                    GetCurrentThreadId(),
                    Context->LoopCounter,
                    g_Target.Field2, g_Field2);
            }
            //g_Target.Field2 = g_FlipFlop;
            SetBit1(&g_Target.Word, g_FlipFlop);
            g_Field2 = g_Target.Field2;
            break;
        }

        //int RandomWait = int(double(RtlRandom(&Context->DynamicSeed))/MAXLONG*10);
        //Sleep(RandomWait);

    }

    return 0;
}

void Test_Bitfield(int NumOfThreads, int Iteration) {
    HANDLE *ThreadPool = new HANDLE[NumOfThreads];
    CONTEXT_CHURN *ThreadContexts = new CONTEXT_CHURN[NumOfThreads];

    if ( ThreadPool && ThreadContexts ) {
        ULONG DynamicSeed = GetTickCount();

        for ( int i=0 ; i<NumOfThreads  ; ++i ) {
            ThreadContexts[i].DynamicSeed = RtlRandom(&DynamicSeed);
            ThreadContexts[i].Iteration = Iteration;
            ThreadContexts[i].ThreadIndex= i;
            ThreadContexts[i].LoopCounter= 0;
            ThreadPool[i] = CreateThread(NULL, 0, ChurningThread, &ThreadContexts[i], CREATE_SUSPENDED, NULL);
        }
   
        g_Target.Field1 = g_Field1;
        g_Target.Field2 = g_Field2;

        for ( int i=0 ; i<NumOfThreads  ; ++i ) {
            if ( ThreadPool[i] ) {
                SetThreadAffinityMask(ThreadPool[i], 2);
                ResumeThread(ThreadPool[i]);
            }
        }

        WaitForMultipleObjects(NumOfThreads, ThreadPool, TRUE, INFINITE);
      
        for ( int i=0 ; i<NumOfThreads  ; ++i ) {
            CloseHandle(ThreadPool[i]);
        }

        delete [] ThreadPool;
        delete [] ThreadContexts;
    }
}

int wmain(int argc, wchar_t *argv[]) {
    NtDllDll = LoadLibrary(NTDLL_DLL);
    RtlRandom = (RTLRANDOM)GetProcAddress(NtDllDll, "RtlRandom");

    if ( argc>=3 ) {
        Test_Bitfield(_wtoi(argv[1]), _wtoi(argv[2]));
    }

    return 0;
}

ビルドが通ったら、MASM のアセンブルが意図した通りになっているか、念のためアセンブラを確認します。uf コマンドだけだと nop がずらーっと表示されてしまうので、find コマンドで nop の行を除外して表示します。

0:000> !! -ci "uf win32c!SetBit0" find /V "nop"
win32c!SetBit0:
00007ff7`0ec51360 448b01          mov     r8d,dword ptr [rcx]
00007ff7`0ec51363 664133d0        xor     dx,r8w
00007ff7`0ec51367 6683e201        and     dx,1
00007ff7`0ec5136b 664433c2        xor     r8w,dx
00007ff7`0ec513a1 66448901        mov     word ptr [rcx],r8w
00007ff7`0ec513a5 c3              ret
.shell: Process exited
0:000> !! -ci "uf win32c!SetBit1" find /V "nop"
win32c!SetBit1:
00007ff7`0ec513a6 448b01          mov     r8d,dword ptr [rcx]
00007ff7`0ec513a9 6603d2          add     dx,dx
00007ff7`0ec513ac 664133d0        xor     dx,r8w
00007ff7`0ec513b0 6683e202        and     dx,2
00007ff7`0ec513b4 664433c2        xor     r8w,dx
00007ff7`0ec513b8 66448901        mov     word ptr [rcx],r8w
00007ff7`0ec513bc c3              ret
.shell: Process exited
0:000> !! -ci "uf win32c!SetBit0Safe" find /V "nop"
win32c!SetBit0Safe:
00007ff7`0ec513bd 66448b01        mov     r8w,word ptr [rcx]
00007ff7`0ec513c1 664433c2        xor     r8w,dx
00007ff7`0ec513c5 664183e001      and     r8w,1
00007ff7`0ec513fc 66443101        xor     word ptr [rcx],r8w
00007ff7`0ec51400 c3              ret
.shell: Process exited
0:000> !! -ci "uf win32c!SetBit1Safe" find /V "nop"
win32c!SetBit1Safe:
00007ff7`0ec51401 66448b01        mov     r8w,word ptr [rcx]
00007ff7`0ec51405 66d1e2          shl     dx,1
00007ff7`0ec51408 664433c2        xor     r8w,dx
00007ff7`0ec5140c 664183e002      and     r8w,2
00007ff7`0ec51411 66443101        xor     word ptr [rcx],r8w
00007ff7`0ec51415 c3              ret
.shell: Process exited
0:000>

そして、以下が手元の環境で実行した結果です。2 億回に数回は起こすことができました。

D:\VSDev\Projects\win32c>x64\Release\win32c.exe 3 200000000
[ChurningThread.03d0] 7238814: g_Target.Field2=1 g_Field2=0
[ChurningThread.03d0] 32023047: g_Target.Field2=1 g_Field2=0
[ChurningThread.03d0] 39249682: g_Target.Field2=1 g_Field2=0

D:\VSDev\Projects\win32c>x64\Release\win32c.exe 3 200000000
[ChurningThread.2558] 30084234: g_Target.Field1=1 g_Field1=0

D:\VSDev\Projects\win32c>x64\Release\win32c.exe 3 200000000
[ChurningThread.1e90] 8601808: g_Target.Field2=0 g_Field2=1
[ChurningThread.1e90] 15811427: g_Target.Field2=1 g_Field2=0
[ChurningThread.1e90] 22964666: g_Target.Field2=1 g_Field2=0
[ChurningThread.1e90] 33260005: g_Target.Field2=0 g_Field2=1

次に SetBit0 と SetBit1 を、それぞれ SetBit0Safe と SetBit1Safe に変更してコンパイルして再度実行します。すると、今度は何回実行しようと競合は発生しませんでした。

というわけで、やはり x64 のコンパイル結果はよろしくないことが分かりました。といっても、Sleep を取っ払って nop を 50 個入れて、その上で 2 億回に数回なので、かなり低い確率ですが。逆に言えば、通常環境で万が一発生した時には極めて再現頻度の低い timing issue ということになります。

最後に、呼び出す関数は SetBit0Safe と SetBit1Safe のままにして、SetThreadAffinityMask の行をコメントアウトしてビルドしたものを実行してみます。つまり、アセンブラ的に OK なものを念のためマルチ プロセッサーで実行してみる検証です。

D:\VSDev\Projects\win32c>x64\Release\win32c.exe 3 50000
[ChurningThread.1650] 7: g_Target.Field1=1 g_Field1=0
[ChurningThread.1f68] 2570: g_Target.Field2=0 g_Field2=1

D:\VSDev\Projects\win32c>x64\Release\win32c.exe 3 50000
[ChurningThread.2308] 1: g_Target.Field1=1 g_Field1=0

D:\VSDev\Projects\win32c>x64\Release\win32c.exe 3 50000
[ChurningThread.0440] 330: g_Target.Field1=0 g_Field1=1
[ChurningThread.1720] 4045: g_Target.Field2=0 g_Field2=1

D:\VSDev\Projects\win32c>x64\Release\win32c.exe 3 50000
[ChurningThread.2504] 54: g_Target.Field1=1 g_Field1=0
[ChurningThread.0464] 1528: g_Target.Field2=0 g_Field2=1
[ChurningThread.0464] 1529: g_Target.Field2=0 g_Field2=1

50000 回に数回の頻度で競合が発生しました。競合の発生頻度に特徴があるように感じます。CPU キャッシュの動作の仕組みを調べてみないと。。。

広告

[windbg] Debugger extension to dump binary tree

先月、ある解析のためにデバッガー拡張 DLL を書いてみたところ、思いのほか簡単だったのでコードを共有します。バイナリ ツリーをダンプするだけのコマンドです。Windows カーネルで多用されているリストについては、dl や !list といった標準コマンドがありますが、ツリーに関してはなさそうだったので作りました。

[2015/2/15 追記]
本記事で紹介しているコードは、ターゲットが 64bit である場合に限定されていました。32bit にも対応するように書き直したコードを GitHub 上で公開しています。コマンドは !dumptree から !dt に変更しました。

https://github.com/msmania/bangon/

実は、Windows には木構造も随所に使われています。今回対象とするのは、Windows カーネルに実装されている RTL_SPLAY_LINKS 構造体です。

RTL_SPLAY_LINKS structure (Windows Drivers)
http://msdn.microsoft.com/en-us/library/windows/hardware/ff553351(v=vs.85).aspx

typedef struct _RTL_SPLAY_LINKS {
  struct _RTL_SPLAY_LINKS  *Parent;
  struct _RTL_SPLAY_LINKS  *LeftChild;
  struct _RTL_SPLAY_LINKS  *RightChild;
} RTL_SPLAY_LINKS, *PRTL_SPLAY_LINKS;

名前の通りスプレー木なので、木の回転が発生しています。データ構造としては、親と左右の子をメンバーに持つごく普通の木です。通常であれば、dt や dq を使ってがりがり値を見ていくところですが、ツリーが大きいと面倒なことこの上ありません。

スプレー木 – Wikipedia
http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%97%E3%83%AC%E3%83%BC%E6%9C%A8

デバッガー拡張 DLL の作り方については、ここが本家です。

Writing WdbgExts Extensions (Windows Debuggers)
http://msdn.microsoft.com/en-us/library/windows/hardware/ff561491(v=vs.85).aspx

デバッガーをインストールした場所の winext フォルダーに入っている DLL のエクスポート関数を見てみると分かりますが、デバッガーの拡張コマンドのそれぞれがエクスポート関数に対応しています。要は、DLL を作ればいいわけです。

image
uext.dll を dependency walker で開いたところ。!handle コマンドなどが見える。

Visual Studio で空の Win32 DLL プロジェクトを作って、以下 3 つのファイル (dllmain.cpp fext.cpp fext.def) を追加します。

dllmain.cpp は DllMain だけです。特に意味はありませんが、エクスポート関数とは別に定義しておくのが好きです。使いまわせるし。

//
// dllmain.cpp
//

#include <windows.h>

BOOL WINAPI DllMain(
  _In_  HINSTANCE hinstDLL,
  _In_  DWORD fdwReason,
  _In_  LPVOID lpvReserved
) {
    switch (fdwReason) {
    case DLL_PROCESS_ATTACH:
    case DLL_THREAD_ATTACH:
    case DLL_THREAD_DETACH:
    case DLL_PROCESS_DETACH:
        break;
    }
    return TRUE;
}

メインのファイルが fext.cpp です。エクスポート関数とその関連定義を全部書きます。ここでインクルードしている wdbgexts.h は、デバッガーをインストールした場所の sdk\inc フォルダー下に入っています。プロジェクト フォルダーにコピーしておくと楽です。

アルゴリズムは・・・Breadth-first search しているだけです。重複ぐらいは確認しています。

//
// fext.cpp
//

#include <Windows.h>
#include <set>
#include <queue>

#include "..\dbgsdk\wdbgexts.h"

#define LODWORD(ll) ((DWORD)(ll&0xffffffff))
#define HIDWORD(ll) ((DWORD)((ll>>32)&0xffffffff))

//
//
http://msdn.microsoft.com/en-us/library/windows/hardware/ff543968(v=vs.85).aspx
//
EXT_API_VERSION ApiVersion = {
    0,    // MajorVersion
    0,    // MinorVersion
    EXT_API_VERSION_NUMBER64,    // Revision
    0    // Reserved
};

//
//
http://msdn.microsoft.com/en-us/library/windows/hardware/ff561303(v=vs.85).aspx
// ExtensionApis is extern defined as WINDBG_EXTENSION_APIS in wdbgexts.h
//
WINDBG_EXTENSION_APIS ExtensionApis;

LPEXT_API_VERSION ExtensionApiVersion(void) {
    return &ApiVersion;
}

VOID WinDbgExtensionDllInit(
  PWINDBG_EXTENSION_APIS lpExtensionApis,
  USHORT MajorVersion,
  USHORT MinorVersion
) {
    ExtensionApis = *lpExtensionApis;
    return;
}

DECLARE_API (help) {
    dprintf("Hello!\n");
}

struct TREE_ITEM64 {
    ULONGLONG Parent;
    ULONGLONG LeftChild;
    ULONGLONG RightChild;
};

struct TREE_ITEM_INFO {
    DWORD Level;
    ULONGLONG Myself;
    TREE_ITEM64 Item;
};

std::queue<TREE_ITEM_INFO> TraverseQueue;
std::set<ULONGLONG> CorruptionCheck;

BOOL AddTreeItem(DWORD Level, ULONGLONG Address) {
    if ( CorruptionCheck.find(Address)!=CorruptionCheck.end() ) {
        return FALSE;
    }

    CorruptionCheck.insert(Address);

    DWORD BytesRead = 0;
    TREE_ITEM_INFO TreeItem;
    TreeItem.Level = Level;
    TreeItem.Myself = Address;
    ReadMemory(Address, &(TreeItem.Item), sizeof(TREE_ITEM64), &BytesRead);

    if ( BytesRead!=sizeof(TREE_ITEM64) ) {
        return FALSE;
    }

    TraverseQueue.push(TreeItem);
    return TRUE;
}

DECLARE_API (dumptree) {
    ULONGLONG RootAddress = GetExpression(args);

    if ( !RootAddress )
        return;
   
    while ( TraverseQueue.size() ) {
        TraverseQueue.pop();
    }
    CorruptionCheck.clear();

    AddTreeItem(0, RootAddress);

    DWORD CurrentLevel = 0;
    DWORD ItemCount = 0;
    while ( TraverseQueue.size() ) {
        const TREE_ITEM_INFO &Item = TraverseQueue.front();

        dprintf("L=%04x#%04x %08x`%08x : P=%08x`%08x L=%08x`%08x R=%08x`%08x\n",
            CurrentLevel, ItemCount,
            HIDWORD(Item.Myself), LODWORD(Item.Myself),
            HIDWORD(Item.Item.Parent), LODWORD(Item.Item.Parent),
            HIDWORD(Item.Item.LeftChild), LODWORD(Item.Item.LeftChild),
            HIDWORD(Item.Item.RightChild), LODWORD(Item.Item.RightChild));
       
        if ( Item.Level!=CurrentLevel ) {
            ItemCount = 0;
            CurrentLevel = Item.Level;
        }
       
        if ( Item.Item.LeftChild ) {
            if ( !AddTreeItem(Item.Level+1, Item.Item.LeftChild) ) {
                dprintf("Item %08x`%08x was duplicated!\n",
                    HIDWORD(Item.Item.LeftChild), LODWORD(Item.Item.LeftChild));
            }
        }

        if ( Item.Item.RightChild ) {
            if ( !AddTreeItem(Item.Level+1, Item.Item.RightChild) ) {
                dprintf("Item %08x`%08x was duplicated!\n",
                    HIDWORD(Item.Item.RightChild), LODWORD(Item.Item.RightChild));
            }
        }

        ++ItemCount;
        TraverseQueue.pop();
    }
}

最後に定義ファイルです。

;
; fext.def
;

LIBRARY "FEXT.dll"
EXPORTS
    WinDbgExtensionDllInit
    ExtensionApiVersion
    help
    dumptree

デバッガーは拡張 DLL を動的リンクするので、ヘッダーは不要です。

これらのファイルをコンパイル/リンクして、x64 ネイティブの DLL を作ります。デバッガーのプロセスが拡張 DLL を直接ロードする以上、デバッガーと DLL の CPU アーキテクチャーの種類は同じでなければなりません。もし、32bit デバッガー用の DLL を作る場合は、fext.cpp の修正も必要です。手元の環境で作成した fext.dll を開いたところです。dumptree という関数が拡張コマンドです。

image

さて、実際に使ってみます。Windows のどこに木構造なんてあるんだ、という話ですが、木のスプレー操作を行うための関数がカーネルに用意されているので、ここでブレークしたパラメーターから木構造を入手できます。RtlSplay という関数の引数がそのまま RTL_SPLAY_LINKS へのポインターになっています。

RtlSplay routine (Windows Drivers)
http://msdn.microsoft.com/en-us/library/windows/hardware/ff553226(v=vs.85).aspx

今回は、Windows 8 x64 の Hyper-V 仮想マシンに対してデバッガーを繋ぎました。ゲスト上で特に何の操作もしていないのですが、すぐにブレークしてくれました。NTFS に木構造があるようです。

kd> x nt!RtlSplay
fffff801`fe0cdd40 nt!RtlSplay (<no parameter info>)
kd> bp nt!RtlSplay
kd> g
Breakpoint 0 hit
nt!RtlSplay:
fffff801`fe0cdd40 483909          cmp     qword ptr [rcx],rcx
kd> .reload
Connected to Windows 8 9200 x64 target at (Sat Nov 30 12:58:10.979 2013 (UTC – 8:00)), ptr64 TRUE
Loading Kernel Symbols
………………………………………………………
……………………………………………………….
………..
Loading User Symbols
……………………………………………………….
.
Loading unloaded module list
……..
kd> k
Child-SP          RetAddr           Call Site
fffff880`04f02bb8 fffff880`0178d25f nt!RtlSplay
fffff880`04f02bc0 fffff880`01786487 Ntfs!NtfsFindPrefix+0x1df
fffff880`04f02c70 fffff880`017824a1 Ntfs!NtfsFindStartingNode+0x537
fffff880`04f02d30 fffff880`01786d0d Ntfs!NtfsCommonCreate+0x401
fffff880`04f02f50 fffff801`fe089767 Ntfs!NtfsCommonCreateCallout+0x1d
fffff880`04f02f80 fffff801`fe08972d nt!KxSwitchKernelStackCallout+0x27
fffff880`044e60e0 fffff801`fe0cff1e nt!KiSwitchKernelStackContinue
fffff880`044e6100 fffff801`fe0d0d85 nt!KeExpandKernelStackAndCalloutInternal+0x20e
fffff880`044e6200 fffff880`0177a7f4 nt!KeExpandKernelStackAndCalloutEx+0x25
fffff880`044e6240 fffff880`015714ee Ntfs!NtfsFsdCreate+0x1d4
fffff880`044e6420 fffff880`0159b35d fltmgr!FltpLegacyProcessingAfterPreCallbacksCompleted+0x25e
fffff880`044e64c0 fffff801`fe45f05b fltmgr!FltpCreate+0x34d
fffff880`044e6570 fffff801`fe45bc5d nt!IopParseDevice+0x77b
fffff880`044e6760 fffff801`fe4612b8 nt!ObpLookupObjectName+0x7a1
fffff880`044e6890 fffff801`fe472ebe nt!ObOpenObjectByName+0x258
fffff880`044e6960 fffff801`fe473609 nt!IopCreateFile+0x37c
fffff880`044e6a00 fffff801`fe08e053 nt!NtCreateFile+0x79
fffff880`044e6a90 000007ff`3ab530fa nt!KiSystemServiceCopyEnd+0x13
000000e7`eed4f128 000007ff`37e952dc ntdll!NtCreateFile+0xa
000000e7`eed4f130 000007ff`37e95411 KERNELBASE!CreateFileInternal+0x324
000000e7`eed4f2b0 000007ff`321b60f9 KERNELBASE!CreateFileW+0x6d
000000e7`eed4f310 000007ff`321b603a sysmain!PfXpGetFileSize+0x39
000000e7`eed4f360 000007ff`321b2ebe sysmain!PfXpSaveLayout+0x10a
000000e7`eed4f620 000007ff`321a6460 sysmain!PfXpUpdateOptimalLayout+0x1e4
000000e7`eed4f790 000007ff`3ab6cd41 sysmain!PfXpTaskCommonCallback+0x40
000000e7`eed4f7c0 000007ff`3ab58576 ntdll!TppExecuteWaitCallback+0x151
000000e7`eed4f830 000007ff`38f4167e ntdll!TppWorkerThread+0x388
000000e7`eed4fad0 000007ff`3ab6c3f1 KERNEL32!BaseThreadInitThunk+0x1a
000000e7`eed4fb00 00000000`00000000 ntdll!RtlUserThreadStart+0x1d
kd> !process -1 0
PROCESS fffffa8002b6d840
    SessionId: 0  Cid: 03fc    Peb: 7f7ab80e000  ParentCid: 0204
    DirBase: 186ba000  ObjectTable: fffff8a005ff0f40  HandleCount: <Data Not Accessible>
    Image: svchost.exe

kd>

ここで拡張 DLL を実行します。.load して呼び出すだけです。

kd> .load D:\MSWORK\fext\fext.dll
kd> !fext.help
Hello!
kd> !fext.dumptree @rcx
L=0000#0000 fffff8a0`00e794c8 : P=fffff8a0`00e794c8 L=fffff8a0`008ee988 R=fffff8a0`00883f28
L=0000#0001 fffff8a0`008ee988 : P=fffff8a0`00e794c8 L=fffff8a0`0603db38 R=fffff8a0`00901988
L=0001#0001 fffff8a0`00883f28 : P=fffff8a0`00e794c8 L=00000000`00000000 R=00000000`00000000
L=0001#0002 fffff8a0`0603db38 : P=fffff8a0`008ee988 L=fffff8a0`020d04c8 R=00000000`00000000
L=0002#0001 fffff8a0`00901988 : P=fffff8a0`008ee988 L=fffff8a0`00987810 R=00000000`00000000
L=0002#0002 fffff8a0`020d04c8 : P=fffff8a0`0603db38 L=00000000`00000000 R=fffff8a0`00986060
L=0003#0001 fffff8a0`00987810 : P=fffff8a0`00901988 L=00000000`00000000 R=00000000`00000000
L=0003#0002 fffff8a0`00986060 : P=fffff8a0`020d04c8 L=00000000`00000000 R=fffff8a0`06104a38
L=0004#0001 fffff8a0`06104a38 : P=fffff8a0`00986060 L=00000000`00000000 R=00000000`00000000
kd> dq @rcx l4
fffff8a0`00e794c8  fffff8a0`00e794c8 fffff8a0`008ee988
fffff8a0`00e794d8  fffff8a0`00883f28 00000000`0022000a
kd>

別のブレークでも試してみました。今度は win32k のようです。スプレーの途中なので、必ずしも木のルートがパラメーターに来るわけではありません。

kd> !process -1 0
PROCESS fffffa80018dd940
    SessionId: 1  Cid: 09a0    Peb: 7f7daf3f000  ParentCid: 0998
    DirBase: 214f8000  ObjectTable: fffff8a00740c9c0  HandleCount: <Data Not Accessible>
    Image: explorer.exe
kd> k
Child-SP          RetAddr           Call Site
fffff880`04fcd518 fffff801`fe0f79eb nt!RtlSplay
fffff880`04fcd520 fffff960`0028d943 nt!RtlLookupElementGenericTable+0x3b
fffff880`04fcd550 fffff960`0028d67d win32k!GreUpdateSprite+0x183
fffff880`04fcd780 fffff960`001e8035 win32k!GreUpdateSpriteDevLockEnd+0x808
fffff880`04fcdab0 fffff960`001e5b5e win32k!DEVLOCKBLTOBJ::~DEVLOCKBLTOBJ+0x165
fffff880`04fcdb00 fffff960`001eb4db win32k!NtGdiBitBltInternal+0x9ce
fffff880`04fcdd60 fffff801`fe08e053 win32k!NtGdiBitBlt+0x5b
fffff880`04fcddd0 000007ff`38d2322a nt!KiSystemServiceCopyEnd+0x13
00000000`0257f058 000007ff`38d231f1 GDI32!NtGdiBitBlt+0xa
00000000`0257f060 000007ff`369273c6 GDI32!BitBlt+0xd1
(Inline Function) ——–`——– UxTheme!CPaintBuffer::_PaintTargetRect+0x5b
(Inline Function) ——–`——– UxTheme!CPaintBuffer::_PaintImmediate+0x134
(Inline Function) ——–`——– UxTheme!CPaintBuffer::EndPaint+0x172
(Inline Function) ——–`——– UxTheme!CPaintBufferPool::Impl::End+0x1a6
(Inline Function) ——–`——– UxTheme!CPaintBufferPool::EndBufferedPaint+0x1a9
00000000`0257f120 000007f7`db5f2637 UxTheme!EndBufferedPaint+0x1f6
00000000`0257f1b0 000007f7`db5f2023 Explorer!CTaskListWnd::_HandlePaint+0x434
00000000`0257f2b0 000007f7`db5f1210 Explorer!CTaskListWnd::v_WndProc+0x6f
00000000`0257f3a0 000007ff`387f3e95 Explorer!CImpWndProc::s_WndProc+0x91
00000000`0257f3e0 000007ff`387f2a62 USER32!UserCallWinProcCheckWow+0x18d
00000000`0257f4a0 000007ff`387f294d USER32!DispatchClientMessage+0xf8
00000000`0257f500 000007ff`3ab54b47 USER32!_fnDWORD+0x2d
00000000`0257f560 000007ff`387f203a ntdll!KiUserCallbackDispatcherContinue
00000000`0257f5e8 000007ff`387f204c USER32!NtUserDispatchMessage+0xa
00000000`0257f5f0 000007f7`db5f1131 USER32!DispatchMessageWorker+0x2af
00000000`0257f670 000007f7`db61b41e Explorer!CTray::_MessageLoop+0x122
00000000`0257f700 000007ff`36641d4c Explorer!CTray::MainThreadProc+0x86
00000000`0257f730 000007ff`38f4167e SHCORE!COplockFileHandle::v_GetHandlerCLSID+0x12c
00000000`0257f820 000007ff`3ab6c3f1 KERNEL32!BaseThreadInitThunk+0x1a
00000000`0257f850 00000000`00000000 ntdll!RtlUserThreadStart+0x1d
kd> !fext.dumptree @rcx
L=0000#0000 fffff901`007780c0 : P=fffff901`007560b0 L=fffff901`0071f1f0 R=fffff901`03c63d30
L=0000#0001 fffff901`0071f1f0 : P=fffff901`007780c0 L=00000000`00000000 R=00000000`00000000
L=0001#0001 fffff901`03c63d30 : P=fffff901`007780c0 L=fffff901`00742230 R=fffff901`03c1f280
L=0001#0002 fffff901`00742230 : P=fffff901`03c63d30 L=fffff901`03c17280 R=fffff901`03c51590
L=0002#0001 fffff901`03c1f280 : P=fffff901`03c63d30 L=00000000`00000000 R=fffff901`03c440c0
L=0002#0002 fffff901`03c17280 : P=fffff901`00742230 L=00000000`00000000 R=fffff901`006e3280
L=0003#0001 fffff901`03c51590 : P=fffff901`00742230 L=00000000`00000000 R=00000000`00000000
L=0003#0002 fffff901`03c440c0 : P=fffff901`03c1f280 L=00000000`00000000 R=fffff901`03c252b0
L=0003#0003 fffff901`006e3280 : P=fffff901`03c17280 L=00000000`00000000 R=00000000`00000000
L=0004#0001 fffff901`03c252b0 : P=fffff901`03c440c0 L=fffff901`0014b240 R=00000000`00000000
L=0004#0002 fffff901`0014b240 : P=fffff901`03c252b0 L=00000000`00000000 R=fffff901`03c4b400
L=0005#0001 fffff901`03c4b400 : P=fffff901`0014b240 L=00000000`00000000 R=00000000`00000000