[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 めんどくさい・・・。

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

Win32 では setbit32.obj をリンク

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 キャッシュの動作の仕組みを調べてみないと。。。