Vectorized computation: R vs Python vs C++

前回のコードで、どうやら Python が遅いらしいことが分かったので、実際に C++ でモジュールを書き始める前に、どのぐらい遅いのかを調べてみることにしました。まずは軽く情報収集。

以下のページによると、Python は動的型付けなので、型チェックのせいで四則演算が遅くなるらしい。これは納得できる。さらに、NumPy は SIMD に対応していて、Cython を使うと速くなるとか。

Pythonを高速化するCythonを使ってみた – Kesin’s diary
http://kesin.hatenablog.com/entry/20120306/1331043675

その一方、R や Python の方が C より速くなる、というような不思議な結果を報告しているページもありました。この結論は原理的におかしいような気もしますが・・。

機械学習序曲(仮) > 数値計算の実行速度 – Python, C, Rの比較
http://hawaii.naist.jp/~kohei-h/my/python-numeric-comp.html

(2015/12/20 – 議論が雑だったので、データを取り直して全体的に修正。)

今回計測したいのは、2 次元ベクトルの四則演算 (オイラー法で、微小時間におけるベクトルの変化を計算するため)、及び、ばねの力を計算するときに使うノルムの計算です。というわけで、SSE や AVX といったベクトル演算用のユニット (= SIMD) をちゃんと使いたいところです。具体的には、こんな計算を計測することにしました。

V1 = V1 + d * V2

V1 と V2 は 2 次元ベクトルを横に P 個並べた行列、d はスカラーで、(0, 1) の範囲乱数を使います。この簡単な加算と乗算を N 回繰り返して速度を測ります。ノルムの演算は気が向いたら後で書き足します。

実行環境は以下の通り。

  • OS: Ubuntu 15.10
  • CPU: Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz (Sandy Bridge)
  • gcc (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010
  • Eigen 3.2.7
  • Python 2.7.10
  • R version 3.2.3 (2015-12-10) — "Wooden Christmas-Tree"

R と Python はそのまま、C++ では 6 つの処理系で比較します。C++ を使った場合の速度の違いで見ておきたいポイントは 2 つあり、一つは SIMD 演算で従来型の SSE を使うか Sandy Bridge から搭載された AVX 命令を使うかどうか、もう一つは、SSE/AVX 演算ユニットのスカラー演算を使うかベクトル演算を使うかという点です。前者は -mavx オプションで制御できます。後者は intrinsic を使って明示的に実装することもできますが、今回は gcc の自動ベクトル化機能を -ftree-vectorize オプションで有効にして利用します。ただし、最適化オプション -O3 を使うと、自動ベクトル化は勝手に行われます。よって、今回はベクトル化演算を行う前提で SSE と AVX でどれだけ違いが出るのかを見るのが趣旨です。というのも、SIMD は本来ベクトル演算向けのユニットなので、スカラー演算で使ってもあまり意味がないからです。

gcc のベクトル化に関しては ↓ が参考になります。

Auto-vectorization in GCC – GNU Project – Free Software Foundation (FSF)
https://gcc.gnu.org/projects/tree-ssa/vectorization.html

まとめるとこんな感じです。

Language Matrix datatype Gcc option SIMD
R num(,) N/A ?
Python numpy.ndarray N/A ?
C++ std::vector -O3 vectorized, SSE
C++ std:valarray -O3 vectorized, SSE
C++ Eigen::MatrixXd -O3 vectorized, SSE
C++ std::vector -O3 -ftree-vectorize -mavx vectorized, AVX
C++ std::valarray -O3 -ftree-vectorize -mavx vectorized, AVX
C++ Eigen::MatrixXd -O3 -ftree-vectorize -mavx vectorized, AVX

で、書いたコードがこれです。いろいろ詰め込んだせいで無駄にファイルが多い。

https://github.com/msmania/ems/tree/perftest

主要なファイルについてはこんな感じ。

  • perftest.R – R の計算ルーチン
  • perftest.py – Python の計算ルーチン
  • perftest.cpp – C++ の計算ルーチン
  • main.cpp – 実行可能ファイル runc 用の main()
  • shared.cpp – Python モジュール化のためのコード
  • common.h / common.cpp – shared.cpp と main.cpp とで共有するコード
  • draw.R – 結果を折れ線グラフで描く R のコード

コードを make すると、Python モジュールとしてインポートできる perftest.so と、スタンドアロンの実行可能ファイルである runc ができます。いずれのファイルにも、AVX を使った場合の関数と、使っていない場合の関数がそれぞれ avx、noavx という名前空間内に作られます。

Makefile の中で、perftest.cpp を別のレシピでコンパイルするようにしました。

override CFLAGS+=-Wall -fPIC -std=c++11 -O3 -g -Wno-deprecated-declarations
VFLAGS=-ftree-vectorize -ftree-vectorizer-verbose=6 -mavx -D_AVX
perftest.o: perftest.cpp
    $(CC) $(INCLUDES) $(CFLAGS) -c $^
perftest_avx.o: perftest.cpp
    $(CC) $(INCLUDES) $(CFLAGS) $(VFLAGS) -c $^ -o $@

-Wno-deprecated-declarations オプションは、Eigen のヘッダーをインクルードしたときに警告が出るので入れています。

では実測タイム。まずは Python から実行。引数の意味は、2 次元ベクトルを 10,000 個並べた行列を 1,000,000 回計算する、という意味です。

john@ubuntu1510:~/Documents/ems$ python perftest.py 10000 1000000
*** Python: numpy.ndarray ***
time = 26.096 (s)
*** R ***
[1] "*** matrix(n, 2) ***"
[1] time = 69.94 (s)
*** C++: no-vectorize no-avx ***
std::vector   time = 11.398 (s)
std::valarray time = 11.371 (s)
Eigen::Matrix time = 10.547 (s)
*** C++: vectorize avx ***
std::vector   time = 10.208 (s)
std::valarray time = 10.221 (s)
Eigen::Matrix time = 10.549 (s)

R 遅すぎ・・・。コンパイルされないからだろうか。Python も C++ と比べると 2 倍以上遅い。C++ については、avx と no-avx を比べると 10% ぐらい avx の方が速そう。もう少し試行回数を増やすため R と Python には退場してもらって、C++ だけ実行します。そんなときに runc を使います。

john@ubuntu1510:~/Documents/ems$ ./runc 10000 1000000 20 > result-O3-1000k
john@ubuntu1510:~/Documents/ems$ R

> source(‘draw.R’)
> drawResult(‘result-O3-1000k’)

runc の stdout への出力結果は R でそのまま読み込めるようにしているので、これをグラフ化します。レジェンドを入れていないので分かりにくいですが、青 = std::vector, 赤 = std::valarray, 紫 = Eigen、また、明るい色が AVX 有、暗い色が AVX 無になっています。

result-O3-1000k

明らかに、AVX 無の vector と valarray は他より遅いです。AVX を使うと約 10% 速度が向上しています。逆に、Eigen は変化なしといってよさそうです。上位 4 つはほとんど差がありませんが、Eigen よりは AVX を使った vector/valarray の方が有利に見えます。

正直、AVX による速度向上が 10% 程度というのは期待外れでした。理想的には、レジスター サイズが xmm 系の 128bit から ymm 系の 256bit になることによって、速度は 2 倍ぐらいになって欲しいのです。本当に AVX が使われているかどうかを確認するため、生成されたアセンブリを見てみます。gdb を使って逆アセンブル結果をファイルに出力します。

john@ubuntu1510:~/Documents/ems$ gdb runc
(gdb) set height 0
(gdb) set logging file perftest.log
(gdb) i func Test
All functions matching regular expression "Test":

File perftest.cpp:
void avx::TestEigen(int, int);
void avx::TestValArray(int, int);
void avx::TestVector(int, int);
void noavx::TestEigen(int, int);
void noavx::TestValArray(int, int);
void noavx::TestVector(int, int);
(gdb) disas avx::TestEigen
(gdb) disas avx::TestValArray
(gdb) disas avx::TestVector
(gdb) disas noavx::TestEigen
(gdb) disas noavx::TestValArray
(gdb) disas noavx::TestVector
(gdb) set logging  off
Done logging to perftest.log.
(gdb) quit

例えばavx::TestVectorをざっと見ると、以下の部分がベクトル演算をしているところです。pd というサフィックスが Packed Double を意味しています。

0x000000000040236b <+1035>:    vmovddup %xmm0,%xmm9
0x000000000040236f <+1039>:    xor    %ecx,%ecx
0x0000000000402371 <+1041>:    xor    %r15d,%r15d
0x0000000000402374 <+1044>:    vinsertf128 $0x1,%xmm9,%ymm9,%ymm9
0x000000000040237a <+1050>:    vmovupd (%r10,%rcx,1),%xmm1
0x0000000000402380 <+1056>:    add    $0x1,%r15d
0x0000000000402384 <+1060>:    vinsertf128 $0x1,0x10(%r10,%rcx,1),%ymm1,%ymm1
0x000000000040238c <+1068>:    vmulpd %ymm9,%ymm1,%ymm1
0x0000000000402391 <+1073>:    vaddpd (%r8,%rcx,1),%ymm1,%ymm1
0x0000000000402397 <+1079>:    vmovapd %ymm1,(%r8,%rcx,1)
0x000000000040239d <+1085>:    add    $0x20,%rcx
0x00000000004023a1 <+1089>:    cmp    %r11d,%r15d
0x00000000004023a4 <+1092>:    jb  0x40237a <avx::TestVector(int, int)+1050>

上記のコードの前半の vmovddup と vinsertf128 で、xmm0 に入っている 128bit の値 (double  2 つ分) を 2 つにコピーして ymm9 にセットします。おそらくこれは乱数の d です。次に、(%r10,%rcx,1) = r10 + (rcx * 1) のアドレスから 32 バイト (16 バイトずつvmovupd とvinsertf128 を使って) コピーして ymm1 にセットします。これは V2 でしょう。ここで AVX 命令を使って、V2 に d をかけて (%r8,%rcx,1) に加算しています。これが V1 になりそうです。このベクトル演算で、4 つの double を同時に処理していることになります。

avx::TestValArray にも同じ処理が見つかります。avx::TestEigen にも packed double を使っているコードは見つかりますが、ymm レジスタを使っていませんでした。これが、AVX の有無で Eigen の速度が変わらない理由として有力です。

0x0000000000402dcf <+511>:    vmovddup %xmm1,%xmm1
0x0000000000402dd3 <+515>:    xor    %eax,%eax
0x0000000000402dd5 <+517>:    nopl   (%rax)
0x0000000000402dd8 <+520>:    vmulpd (%r12,%rax,8),%xmm1,%xmm0
0x0000000000402dde <+526>:    vaddpd (%rbx,%rax,8),%xmm0,%xmm0
0x0000000000402de3 <+531>:    vmovaps %xmm0,(%rbx,%rax,8)
0x0000000000402de8 <+536>:    add    $0x2,%rax
0x0000000000402dec <+540>:    cmp    %rax,%rbp
0x0000000000402def <+543>:    jg     0x402dd8 <avx::TestEigen(int, int)+520>

AVX 命令の利点の一つとして、従来の SSE 命令のオペランドの数が 2 つだったのに対し、AVX では 3 または 4 オペランドを使用できるようになっています。したがって、計算によっては mov の数を減らすことができるのですが、今回の例ではあまりそれは活きないのかもしれません。

ちなみに -O3 を -O2 に変更した場合、つまり SSE のスカラー演算と AVX のベクトル演算を比較すると、以下のように速度差がより顕著になります。この場合の Eigen のグラフを見るだけでも分かりますが、Eigen は最適化オプションが -O2 であってもベクトル化演算のコードを生成しています。

result-O2

手元に Sandy Bridge 以前の CPU があったので、ベクトル化の有無で速度の違いを比べてみました。コンパイル時に gcc によるベクトル化に失敗したので、コンパイル オプションによる違いはなく、明らかに速度が Eigen > valarray > vector の順になっています。

CPU: AMD Athlon(tm) 64 X2 Dual Core Processor 3800+
result-AMD

というわけで結果からの考察。

  1. 特に工夫をしない場合、R と Python は遅い。
  2. SIMD を意識せずに書いた単純な C++ のループでも、ベクトル化 + AVX によって明白に速度向上が見込める。 というわけで何らかの方法 (既存のライブラリ、intrinsic、gcc のオプション) で必ずベクトル化はしておくべき。
  3. 明白な理由がない限り、 vector を使って自分でループを書くよりは、valarray の四則演算を使っておいた方が利点が多い。ベクトル化 + AVX を使った場合に両者の速度差はほとんどない上、valarray の方がコードが見やすい。 ただし、複雑な演算の時に、vector を使った方がループを工夫できる可能性はあるかも。
  4. Eigen は gcc の自動ベクトル化に頼らず自力でベクトル演算を使える。ただし (現バージョンの 3.2.7 では) AVX を有効にしても ymm レジスタを使わない。Sandy Bridge 以前の CPU では Eigen を使えば間違いない。Sandy Bridge 以降だと、valarray で間に合う演算であれば valarray を使う方がよい。

ただし上記は、SIMD を特に意識せずに C++ を書いた場合なので、intrinsic などを使えばもっと効率よくベクトル化の恩恵を受けられるかもしれません。もちろん、計算アルゴリズムやベクトルのサイズなどが大きく関係してくるので、一概にどれがベストと言い難いのですが、少なくとも、配列要素のアラインメントも特に指定しない単純なループでさえ、自動ベクトル化と AVX はそれなりに効果があるということが分かりました。この速度比較は、それだけで別のテーマになりますが今回はここまでにして、オイラー法は valarray でやってみようかな・・。

Skylake の Xeon モデルには 512bit レジスターを使う AVX3 ユニットが搭載されているらしい。これは使ってみたい。

16bit programming in Windows 95

前回 MS-DOS で QuickAssembler を動かしてみたのはいいものの、32bit のアセンブリ言語をコンパイルできないことに気づいてしまったので、結局 Windows を入れることに。

しかし Hyper-V で Windows 95 のインストーラーを実行すると、仮想マシンがハングしてしまう現象に遭遇。Windows 95 のインストーラーはマウスに対応しているため、このハングの原因はおそらく MS-DOS の MOUSE コマンドを実行するとハングしてしまう現象と同じ気がします。Hyper-V 使えないじゃん、ということで ESXi 5.1 で試してみたら、こちらは問題なし。やっぱり開発用途には VMware に軍配が上がります。

OS のインストール後、開発環境として最初は何も考えずに Visual C++ 6.0 を入れてみたのですが、Visual C++ 6.0 は 16bit アプリケーションの開発に対応していなかった、ということに初めて気づき、以下の 2 つを入れ直しました。何とも世話の焼ける・・

  • VIsual C++ 1.52
  • MASM 6.11

セットアップ中の画面の一部を紹介します。まずは Windows 95。実に懐かしい。

image image

image

十数年ぶりに触ってみると、今では当然のように使っている機能がまだ実装されていなくて驚きます。例えば・・

  • コマンド プロンプトが cmd.exe じゃなくて command.com
  • コマンド プロンプトで矢印キー、 Tab キーが使えない
  • コマンド プロンプトで、右クリックを使ってクリップボードからの貼り付けができない
  • メモ帳で Ctrl+A、Ctrl+S が使えない
  • エクスプローラーにアドレスバーがない

以下は Visual C++ と MASM のインストール画面を抜粋したもの。

image image

MASM 6.11 のインストーラーは CUI。

image

DOS, Windows, WIndows NT の全部に対応しているらしい。

image

MASM はいろいろと注意事項が多い。

image image

image

インストールが完了したら、環境変数の設定を行なうためのバッチ ファイルを作ります。サンプルのスクリプトがインストールされているので、それを組み合わせるだけです。

@echo off
set PATH=C:\MSVC\BIN;C:\MASM611\BIN;C:\MASM611\BINR;%PATH%
set INCLUDE=C:\MSVC\INCLUDE;C:\MSVC\MFC\INCLUDE;C:\MASM611\INCLUDE;%INCLUDE%
set LIB=C:\MSVC\LIB;C:\MSVC\MFC\LIB;C:\MASM611\LIB;%LIB%
set INIT=C:\MSVC;C:\MASM611\INIT;%INIT%

MASM、VC++ ともに NMAKE を持っていますが、VC++ 1.52 に入っている NMAKE のバージョンが新しかったので、VC++ を先頭にしました。

環境ができたところで、今回は 「はじめて読む 486」 の例題を試してみます。本文に掲載されている例題は、Borland C++ 3.1/Turbo Assembler 3.2 用の文法になっているため、細かいところは VC++/MASM 用に書き換えないといけません。というわけでこんな感じ。

まずは C ソースファイル main.c。

#include <stdlib.h>
#include <stdio.h>

extern short GetVer();
extern void RealToProto();
extern void ProtoToReal();

void main(int argc, char **argv) {
    printf("Hello, MS-DOS%d!\n", GetVer());
    RealToProto();
    ProtoToReal();
    printf("Successfully returned from Protected mode.\n");
    exit(0);
}

次がアセンブリ utils.asm。

.386
.MODEL small
.code

;* GetVer – Gets DOS version.
;*
;* Shows:   DOS Function – 30h (Get MS-DOS Version Number)
;*
;* Params:  None
;*
;* Return:  Short integer of form (M*100)+m, where M is major
;*          version number and m is minor version, or integer
;*          is 0 if DOS version earlier than 2.0

_GetVer  PROC

        mov     ah, 30h                 ; DOS Function 30h
        int     21h                     ; Get MS-DOS version number
        .IF     al == 0                 ; If version, version 1
        sub     ax, ax                  ; Set AX to 0
        .ELSE                           ; Version 2.0 or higher
        sub     ch, ch                  ; Zero CH and move minor
        mov     cl, ah                  ;   version number into CX
        mov     bl, 100
        mul     bl                      ; Multiply major by 10
        add     ax, cx                  ; Add minor to major*10
        .ENDIF
        ret                             ; Return result in AX

_GetVer  ENDP

public _RealToProto
_RealToProto    proc    near
                push bp
                mov bp, sp
                ;
                mov eax, cr0
                or eax, 1
                mov cr0, eax
                ;
                jmp flush_q1
flush_q1:
                pop bp
                ret
_RealToProto    endp

public _ProtoToReal
_ProtoToReal    proc    near
                push bp
                mov bp, sp
                ;
                mov eax, cr0
                and eax, 0fffffffeh
                mov cr0, eax
                ;
                jmp flush_q2
flush_q2:
                pop bp
                ret
_ProtoToReal    endp

        END

最後に Makefile。QuickC のときよりは現在の書式に近づきましたが、相変わらずリンカへの入力の渡し方がおかしい。

PROJ = TEST
USEMFC = 0
CC = cl
ML = ml
CFLAGS =/nologo /W3 /O /G3
LFLAGS =/NOLOGO /ONERROR:NOEXE
AFLAGS =
LIBS =
MAPFILE =nul
DEFFILE =nul

all: $(PROJ).EXE

clean:
    @del *.obj
    @del *.exe
    @del *.bnd
    @del *.pdb

UTILS.OBJ: UTILS.ASM
    $(ML) $(AFLAGS) /c UTILS.ASM $@

MAIN.OBJ: MAIN.C
    $(CC) $(CFLAGS) /c MAIN.C $@

$(PROJ).EXE:: MAIN.OBJ UTILS.OBJ
    echo >NUL @<<$(PROJ).CRF
MAIN.OBJ +
UTILS.OBJ
$(PROJ).EXE
$(MAPFILE)
$(LIBS)
$(DEFFILE)
;
<<
    link $(LFLAGS) @$(PROJ).CRF
    @copy $(PROJ).CRF $(PROJ).BND

プログラムはとても単純で、前回と同様に int 21 で DOS のバージョンを表示してから、コントロール レジスタ 0 の PE ビットを変更して特権レベルを変更し、また戻ってくる、というものです。ただし上記のコードでは、C、アセンブリのコンパイルは通るものの、以下のリンクエラーが出てうまくいきません。

UTILS.OBJ(UTILS.ASM) : fatal error L1123: _TEXT : segment defined both 16- and 32-bit

image

ここで 2 時間ぐらいハマりました。リンクエラーの原因は単純で、VC++ 1.52 のコンパイラは 16bit コードを生成しているのに対し、MASM は 32bit コードを生成しているためです。エラー メッセージの通り、16bit と 32bit の 2 つのコード セグメントを含む実行可能ファイルを生成できないためのエラーです。

このプログラムで確かめたいのは、16bit リアル モードから PE ビットを変更してプロテクト モードに移行し、再び 16bit リアル モードに戻ってくる動作です。したがって生成されるべき EXE は 16bit アプリケーションであり、VC++ の生成する main.obj は問題なく、MASM が 16bit コードを生成するように指定したいところです。

MASM が 32bit コードを生成する理由は、utils.asm の先頭の .386 で CPU のアーキテクチャを指定しているためです。これがないと、32bit レジスタの eax などが使えません。CPU のアーキテクチャを指定したことで、その後の .code セグメント指定が自動的に 32bit コード セグメントになってしまっています。

32bit 命令を有効にしつつ、セグメントは 16bit で指定する方法が見つかればよいわけです。NASM や GNU Assembler だと簡単に指定できるようですが・・いろいろと探して、以下のフォーラムを見つけました。10 年前に同じ悩みを抱えている人がいた!

Link Fatal Error 1123
http://www.masmforum.com/board/index.php?PHPSESSID=786dd40408172108b65a5a36b09c88c0&topic=1382.0

ファイルの先頭で .MODEL と CPU 指定を入れ替えればいいらしい。こんなん知らんて。

.MODEL small
.386

.code

;* GetVer – Gets DOS version.
;*
;* Shows:   DOS Function – 30h (Get MS-DOS Version Number)
;*
;* Params:  None
;*
;* Return:  Short integer of form (M*100)+m, where M is major
;*          version number and m is minor version, or integer
;*          is 0 if DOS version earlier than 2.0

_GetVer  PROC

以下、ずっと同じなので省略

これで無事ビルドが成功し、実行できました。文字が出力されているだけなので、本当にプロテクト モードに変わったかどうか疑わしくはありますが、まあ大丈夫でしょう。16bit の道は険しい。

image

MS-DOS 6.22 on Hyper-V

CPU の仕組みについて書かれた本の中でも、「はじめて読む 486」 はかなり有名な名著と言えるはずです。

はじめて読む486―32ビットコンピュータをやさしく語る
http://www.amazon.co.jp/%E3%81%AF%E3%81%98%E3%82%81%E3%81%A6%E8%AA%AD%E3%82%80486%E2%80%9532%E3%83%93%E3%83%83%E3%83%88%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%82%92%E3%82%84%E3%81%95%E3%81%97%E3%81%8F%E8%AA%9E%E3%82%8B-%E8%92%B2%E5%9C%B0-%E8%BC%9D%E5%B0%9A/dp/4756102131

途中で挫折していたので、最初からちゃんと読んでいたところ、やっぱり実機でサンプル コードを試したくなります。ちょっと前にブート コードの勉強をしていたときは、仮想ディスク (VHD) のマスター ブート レコード (MBR) をエディタで書き換えて、 Hyper-V の仮想マシンをその VHD から起動して動かすというけっこう面倒な方法を取っていました。

もっと楽に 16 ビット リアルモードで遊べる環境を作っておこう、ということで、MS-DOS を Hyper-V 仮想マシンにインストールしてみました。何も MS-DOS まで遡らなくても、Windows 9x や ME の DOS モードを使えばいいのですが、まあそこは好奇心ということで。どうでもいい昔話をすると、初めてプログラミングというものに触れたのが中一のときに学校にあった PC-9801 の N88-BASIC で、その後すぐに Windows 95 (年から考えると 98 だったかも) が導入されて Visual Basic/Visual C++ で遊び始めたので、Windows 以前の MS-DOS は全然触ったことがありません。そういえば当時の起動フロッピー ディスクはまだ手元にあるかも・・。

閑話休題、MS-DOS ですが、インストーラーは MSDN サブスクリプションに MS-DOS 6.0 と 6.22 が含まれていたのでそれを使います。MSDN を持っていない人は、"MS-DOS 6.22 download" とかのキーワードでググると、見つかるはずなので自己責任でどうぞ。

手順は以下の通り。6.22 はアップグレード用で、新規インストールはできないので、6.0 を入れてから 6.22 にアップグレードします。

  1. 適当な Windows マシンで MS-DOS 起動ディスクを作る
  2. MSDN からインストールしたファイルを仮想フロッピー、もしくは VHD にコピー
  3. 起動ディスクから DOS を起動
  4. MS-DOS 6.0 をフロッピーにインストール
  5. MS-DOS 6.0 を起動
  6. MS-DOS 6.22 を VHD にインストール

MSDN でダウンロードできるインストーラー en_msdos60.exe や en_msdos622.exe は自己解凍書庫で、解凍すると MS-DOS アプリの setup.exe が出てきます。これを使うためにはそもそも DOS を起動しないといけません。ということで、まずは DOS の起動ディスクを作らないといけません。

まずは空の仮想フロッピー ファイル (.vfd) を作ります。普通は PowerShell の New-Vfd コマンドレットを使うところですが、このコマンドレットは規定サイズの空ファイルを作っているだけなので、fsutil でも代用できます。サイズの 1474560 = 1440 * 1024 は、2HD フロッピーのバイト数です。

D:\MSWORK\dos> fsutil file createnew floppy.vfd 1474560
File D:\MSWORK\dos\floppy.vfd is created

これを仮想マシンにマウントし、エクスプローラーからフォーマットの画面を起動すると、なんと Windows 8.1 でも "Create an MS-DOS startup disk" のチェックボックスが使えます。よく廃止されないものです。ちなみに FORMAT コマンドにはそれに該当するようなオプションは見当たりません。GUI でしかできないんでしょうかね。

01

次に仮想マシンを作ります。RAM は 32MB、HDD は 1GB にしておきます。仮想 BIOS の設定で、Floppy を一番上に移動させます。こんな感じです。

image

先ほど作った起動ディスクをマウントして起動すると、無事 DOS が起動します。バージョンは Windows Millenium [Version 4.90.3000] だそうです。すぐには使わないので、仮想マシンはシャットダウンします。shutdown コマンドなんておものは存在せず、いきなり Turn off で問題ありません。

image

さて次に、DOS インストーラーの準備ですが、MS-DOS 6.0、6.22 共にインストール ファイルの合計サイズが 1.44MB を超えるので、VFD ではなく VHD で作ります。MS-DOS 6.22 の方は、親切にも複数のディスク イメージ ファイル (.img) をそれぞれフロッピーに書き込むためのスクリプトが用意されていますが、ディスクの入れ替えが面倒なだけなので使いません。

New-VHD コマンドレットなどで VHD を作って、MBR ディスクとして初期化し、FAT でフォーマットします。NTFS だと読めないので注意です。インストーラーのファイルは、おそらくドライブのルート ディレクトリ直下に入れておかないと動かないはずなので、それぞれのインストール用 VHD を作らないといけません。

作った VHD を仮想マシンにマウントし、再度起動ディスクから DOS を起動します。構成はこんな感じ。

image

1GB の VHDX はまだフォーマットされていないので認識されず、C: がインストーラーのドライブになります。したがって、C:\SETUP と実行します。

image

なぜか認識できないパーティションがあるとか言われます。よく分からないのでそのまま続行します。

image

MS-DOS 6.0 のインストーラーにはハード ディスクをフォーマットする機能が含まれず、空のハードディスクが見つからなかったため、フロッピーにインストールすることになります。仮にフォーマット済みの VHD をマウントして VHD にインストールしようとしても、有効な DOS が見つかりませんでした、というエラーが出てインストールできないので、最初の MS-DOS はフロッピーにインストールする必要があります。とりあえずこの画面ではそのまま Enter キーを押します。

image

この画面も Enter で続行します。

image

フロッピーを入れろと言われるので、ここで新たに VFD ファイルを作ってマウントしてから Enter キーを押します。

image

フロッピーの種類を聞かれるので、1.44MB を選びます。

image

無事終わりました。Enter キーを押してインストーラーを終了します。

image

元の DOS 画面でエラーが出ますが、おそらく起動ディスクを抜いてしまったためなので、気にせず仮想マシンを再起動します。

image

無事、MS-DOS 6.00 が起動しました。

image

次に MS-DOS 6.22 のインストールに移ります。手順はほとんど同じです。今度はハードディスクにインストールしたいので、インストール先の VHD を予め FAT でフォーマットしておきます。

今度は C: が空ディスク、D: がインストーラーなので D:\SETUP と実行します。

image

また未フォーマットのパーティションが検出されます。そんなのどこにあるんだ・・・気にせず続行します。

image

今度は最小構成ではなく、通常の構成でハードディスクにインストールしてくれそうです。ここも Enter を押します。

image

アンインストール ディスクというものを作る必要があるようです。今でいうリカバリ ディスクでしょうか。ここではそのまま Enter を押します。いちいちラベルを貼る猶予を与えてくれる親切設計。

image

インストール設定の確認です。C:\DOS にインストールされるようです。これぞ C:\WINDOWS の前身!

image

オプションのソフトウェアについて聞かれます。この当時のアンチ ウィルスって一体。Undelete ってのも謎。ごみ箱的な機能・・?とりあえず全部インストールしておきます。

image

いよいよ開始です。

image

フロッピーを入れ替える時間です。

image

サイズは 1.44MB です。

image

まさかのインストール エラー。ISK って何のことか分からず、わりと為す術がない。最初からのステップを 2 回繰り返しましたが、このエラーは変わらず。同じファイルを別の Windows 8.1 上の Hyper-V で試したら特にエラーは出ないので、Windows Server 2012 の Hyper-V との相性が悪いとかだったりして。詳細は不明です。

image

一応インストールは終わりました。フロッピーを抜いて Enter を押します。

image

Enter を押して再起動します。

image

起動には問題ないようです。HIMEM ってやつが結構遅い。

image

次に、どこからともなく入手してきた QuickC with Quick Assembler 2.51 をインストールします。ディスクが 10 枚もあって面倒くさい・・。

image

インストール後、何やら重要そうなことが書かれている画面が出てくるのでキャプチャーしておく。

image

インストールが終わったら、先ほどキャプチャーした画面の記述にしたがって環境変数の設定。現在の C:\AUTOEXEC.BAT はこんな感じ。

@ECHO OFF
PROMPT $p$g
PATH C:\DOS
SET TEMP=C:\DOS

これを、C:\QC25\BIN\NEW-VARS.BAT を参考にして、以下のように変更。MOUSE コマンドを実行してマウス ドライバーを有効にすると、高確率で OS がハングするので、マウスは諦めます。

@ECHO OFF
PROMPT $p$g
SET PATH=C:\QC25\BIN;C:\QC25\TUTORIAL;C:\DOS

SET LIB=C:\QC25\LIB
SET INCLUDE=C:\QC25\INCLUDE

SET TEMP=C:\DOS

あと config.sys。懐かしすぎる。C:\QC25\BIN\NEW-CONF.SYS には FILES=20, BUFFERS=10 と書かれていましたが、FILES は既に 30 になっていたので、BUFFERS を多めの 20 にしておくことに。

DEVICE=C:\DOS\SETVER.EXE
DEVICE=C:\DOS\HIMEM.SYS
DOS=HIGH
FILES=30
SHELL=C:\DOS\COMMAND.COM C:\DOS\  /p
BUFFERS=20

再起動して、早速 QuickC を起動。

image

これが 20 年前の IDE 。。というか画面ちっさ。Hyper-V のせいだけど。

image

ただ普通に Hello World を書いても面白くないので、以下のような 3 つのファイルを書いて NMAKE でビルド。

まずは C のソース。これは普通です。

//
// 00.C
//

#include <stdio.h>

extern int GetVer();

void main(int argc, char **argv)
{
    printf("Hello, MS-DOS %d!", GetVer());
    exit(0);
}

次にアセンブリ言語。サンプルからコピペしただけです。int 21 でバージョンが返ってくるみたいです。

;
; UTILS.ASM
;

    .MODEL    small, c
    .CODE

;* GetVer – Gets DOS version.
;*
;* Shows:   DOS Function – 30h (Get MS-DOS Version Number)
;*
;* Params:  None
;*
;* Return:  Short integer of form (M*100)+m, where M is major
;*        version number and m is minor version, or 0 if
;*        DOS version earlier than 2.0

GetVer    PROC

    mov    ah, 30h       ; DOS Function 30h
    int    21h           ; Get MS-DOS Version Number
    cmp    al, 0         ; DOS version 2.0 or later?
    jne    @F            ; Yes?    Continue
    sub    ax, ax        ; No?  Set AX = 0
    jmp    SHORT exit    ;   and exit
@@:    sub    ch, ch     ; Zero CH and move minor
    mov    cl, ah        ;   version number into CX
    mov    bl, 100
    mul    bl            ; Multiply major by 10
    add    ax, cx        ; Add minor to major*10
exit:    ret             ; Return result in AX

GetVer    ENDP

    END

最後が MAKEFILE。サンプルのファイルを元にいろいろと修正しましたが、リンカの設定のところが意味不明・・。

PROJ    =TEST
CC      =qcl
AS      =qcl
CFLAGS=/Od /Gi$(PROJ).mdt /DNDEBUG /Zi /Zr
AFLAGS=/Zi /Cx /P1
LFLAGS  =/NOI /INCR /CO

.asm.obj: ; $(AS) $(AFLAGS) -c $*.asm

all:    $(PROJ).EXE

utils.obj:        utils.asm

00.obj: 00.c

$(PROJ).EXE:    utils.obj 00.obj
    echo >NUL @<<$(PROJ).crf
utils.obj +
00.obj
$(PROJ).EXE
NUL.MAP

<<
    ilink -a -e "qlink $(LFLAGS) @$(PROJ).crf" $(PROJ)

ファイルを作ったら NMAKE するだけです。

image

おお、MS-DOS のバージョンが出た!これでリアルモードと仲良くできそう。

image

しかしファイルの編集がやりにくすぎる・・・SSH みたいなリモート接続はできないのだろうか。そもそも Hyper-V の仮想 NIC に対応している TCP/IP のドライバーなんてなさそう。

Reflective DLL Injection

社内のツールで、任意のプロセスに対して DLL のコードを埋め込んでそれを呼び出すツールがありました。そのソースを見ると、VirtualAllocEx、WriteProessMemory、そして CreateRemoteThread を使ってけっこう簡単に他プロセスへのコードの埋め込みを実現していました。

VirtualAllocEx function (Windows)
https://msdn.microsoft.com/en-us/library/windows/desktop/aa366890(v=vs.85).aspx

CreateRemoteThread function (Windows)
https://msdn.microsoft.com/en-us/library/windows/desktop/ms682437(v=vs.85).aspx

何これ超便利・・・と感動しつつこの方法についてググると、かなり古くから知られた手法の一つのようで、"createremotethread virtualallocex コード" などのキーワードで日本語のサイトもたくさんヒットします。検索上位に来て分かりやすいのが↓あたり。CreateRemoteThread 以外にも、ウィンドウのサブクラス化を使う方法がメジャーなようです。

ドリーム工房 – デスクトップを乗っ取る
http://www18.atpages.jp/skydreamer/maniax/desktop.php

別のプロセスにコードを割り込ませる3つの方法 – インターネットコム
http://internetcom.jp/developer/20050830/26.html

上記の一つ目のサイトで紹介されている方法は、事前にアセンブリ言語で書いておいたペイロードを WriteProcessMemory でターゲットに埋め込んでおいて、そのアドレスを開始アドレスとしてCreateRemoteThreaad を呼び出しています。ペイロードの中に LoadLibrary する DLL のファイル名をハードコードして、LoadLibrary を直接アドレス指定で call しています。

二つ目のサイトの方法はもっと単純で、開始アドレスを LoadLibrary のアドレスにし、リモートスレッドのパラメーターとして、予めターゲットに埋め込んておいた DLL のファイル名となる文字列のアドレスを渡すというものです。

これらの方法は、Kernel32.dll に実装された LoadLibrary() のエントリポイント (実体は kernelbase.dll) がプロセス間で共有であるという前提に基づいています。この前提については、上記 internetcom.jp の 「付録 A)なぜKERNEL32.DLLとUSER32.DLLは常に同じアドレスにマッピングされるのか」 で説明されています。

これだけでも十分に実用に値するのですが、個人的にはちょっとエレガントさに欠ける気がします。そもそも、kernel32.dll が同じところにマップされるという前提に依存するのがあまり美しくないのですが、もう一つ問題点があります。インジェクターとターゲットのビット数が違うときに、LoadLibrary のアドレスをインジェクター側で取得できないという点です。インジェクターが 64bit プロセスのときは、64bit kernel32.dll 上の LoadLibrary のアドレスが取得できますが、ターゲットが 32bit のときにこれは使えません。逆の場合も同じです。とはいっても些細な問題であり、32bit と 64bit それぞれのインジェクターを用意すればいいだけの話ですが、ターゲットによってインジェクターを変えるのはやはり美しくないのです。

後始末の問題もあります。ターゲットの中で LoadLibrary を実行することができれば、ロードした DLL の DllMain が呼ばれるので、そこからまた新たに新しいスレッドを作るなどして任意のコードを実行させることができます(ローダーロックの問題があるので、DllMain 関数自体はさっさと終わらせないとおかしなことになる、はず。)。また、立つ鳥跡を濁さず、という諺もあるように、全てが終わった後は DLL は FreeLibrary され、さらに VirtualAllocEx しておいたメモリ領域も解放されている、というのが日本的美的センスから見た美しいコード インジェクションではないでしょうか。

簡単そうなのは、ターゲットプロセスではなくインジェクターで後処理を行う方法です。これは上記のinternetcom.jp で紹介されています。メモリ領域の解放は単純に VirtualFreeEx を呼ぶだけですが、FreeLibrary には少しトリックが必要です。というのも、FreeLibrary を呼ぶためには、LoadLibrary からの戻り値である HMODULE、すなわちロードされた DLL のベース アドレスが必要だからです。紹介されている例では、CreateRemoteThread で起動したリモートスレッドが終了するまで待機してから、ベース アドレスをスレッドの終了コードとして GetExitCodeThread を使って取得しています。これはなかなか面白い方法ですが、64bit だと使えないはずです。なぜなら、スレッドの開始関数である LPTHREAD_START_ROUTINE は、本来 DWORD を返すことが想定されており、GetExitCodeThread で取得できるのも DWORD の 32bit 整数だけです。64bit では当然 HMODULE も 64bit アドレスなので、GetExitCodeThread だと、イメージベースの 上位 32bit を取得できません。そのほかの方法として、インジェクトしたコードの中でイメージベースをバッファー内に書き込んでおいて、それをインジェクター側から参照する方法が考えられます。これなら任意のサイズのデータをターゲットからインジェクターに返すことができるので、64bit でも問題はありません。ただ、そもそものデザインとして、インジェクター側でリモート スレッドの終了を待機するのは不満です。

というわけで、後処理をターゲット内で行う方法を考えます。ターゲット内で後処理を行う場合、単純な関数呼び出しで FreeLibrary や VirtualFree を実行して後処理を行うと、制御が戻ってきたときのリターン アドレスが解放済みになってしまうため、アクセス違反が起こります。これもいわゆる use-after-free でしょうか。

そこでまず、FreeLibrary は DLL 外部から実行する必要があります。これは上述の 1 つ目のサイト (ドリーム工房) で紹介されている方法のように、アセンブリで書いたシェルコードを用意してそこから LoadLibrary/FreeLibrary を呼べば解決です。

シェルコードがあるのであれば、メモリ解放についても、VirtualFree をそのまま call するのではなく、スタックを自分で積んでから jmp で VirtualFree を実行することで、VirtualFree 実行後のコード位置を指定して use-after-free 問題を解決できそうです。

アセンブリでシェルコードを書く場合でも、ドリーム工房の方法のように、インジェクター側で取得したアドレスをシェルコードに動的に埋め込むことは可能です、が、何とかしてシェルコード内でイメージベースのアドレスを取得したいところです。そんな方法はないものかと探したところ、けっこう簡単に見つかりました。それがこれ、今回の記事のタイトルにした Reflective DLL Injection。

GitHub – stephenfewer/ReflectiveDLLInjection
https://github.com/stephenfewer/ReflectiveDLLInjection/

ポイントは dll/src/ReflectiveLoader.c に実装された ReflectiveLoader という関数です。そういえば昔覚えたことをすっかり忘れていましたが、Windows では、セグメント レジスタ fs または gs が指すセグメントに PEB や TEB を保存しています。覚えておくとけっこう使えます。

Wikipedia にも情報があります。

Win32 Thread Information Block – Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Win32_Thread_Information_Block

このセグメントレジスタはけっこう身近なところでも使われています。最たる例は、GetLastError() や GetCurrentProcessId() で、x86/x64 それぞれのアセンブリを示すとこんな感じです。また、ちゃんと確かめていませんが、metasploit で遊んでいた時に meterpreter の先頭のコードでもセグメント レジスタを見ていた記憶があります。

0:000> uf kernelbase!GetLastError
KERNELBASE!GetLastError:
775cecd0 64a118000000    mov     eax,dword ptr fs:[00000018h]
775cecd6 8b4034          mov     eax,dword ptr [eax+34h]
775cecd9 c3              ret
0:000> uf kernelbase!GetCurrentProcessId
KERNELBASE!GetCurrentProcessId:
7767cf60 64a118000000    mov     eax,dword ptr fs:[00000018h]
7767cf66 8b4020          mov     eax,dword ptr [eax+20h]
7767cf69 c3              ret

0:000> uf kernelbase!GetLastError
KERNELBASE!GetLastError:
00007ffe`d4f21470 65488b042530000000 mov   rax,qword ptr gs:[30h]
00007ffe`d4f21479 8b4068          mov     eax,dword ptr [rax+68h]
00007ffe`d4f2147c c3              ret
0:000> uf kernelbase!GetCurrentProcessId
KERNELBASE!GetCurrentProcessId:
00007ffe`d4f98b60 65488b042530000000 mov   rax,qword ptr gs:[30h]
00007ffe`d4f98b69 8b4040          mov     eax,dword ptr [rax+40h]
00007ffe`d4f98b6c c3              ret

上記関数は、TEB にある情報を使うので、x86 では fs:18h、x64 では gs:30h のアドレスが TEB であると分かります。

Reflective DLL Injection は、PEB にあるロード済みモジュールのリストからイメージ ベースを取得しています。以下の MSDN に書かれているように、PEB::Ldr->InMemoryOrderModuleList が示すデータには、ロード済みモジュールの名前とベースアドレスの双方向リンクト リストが入っています。

PEB structure (Windows)
https://msdn.microsoft.com/en-us/library/windows/desktop/aa813706(v=vs.85).aspx

PEB_LDR_DATA structure (Windows)
https://msdn.microsoft.com/en-us/library/windows/desktop/aa813708(v=vs.85).aspx

というわけで、以下のロジックをアセンブリで書いて CreateRemoteThread で埋め込めば、まさに実現したい動作が可能です。

  1. セグメント レジスタから PEB を取得
  2. PEB からロード済モジュール リストを取得
  3. リストから Kernel32.dll のベースアドレスを取得
    (ユーザーモード プロセスに kernel32.dll は必ずロードされていると考えてよい)
  4. ベースアドレスから PE イメージの構造を解析し、エクスポート テーブルを取得
  5. エクスポート テーブルを検索して LoadLibrary の開始アドレスを取得

少々めんどくさそうですが、一旦 C で書いて、コンパイルされたアセンブリを整形すればそれほど難しくはないはずです。

この方法を使えば、LoadLibrary だけでなく、シェルコードの中で実行したい API のアドレスを全部取得することができます。また、本記事とは関係ありませんが、コード領域内をパターン検索すれば、エクスポートされていない関数のアドレスも探せるはずです。とにかく、これで後片付けの問題は解決しました。すなわち、シェルコードを以下のようなロジックにします。

  1. LoadLibrary で好きな DLL をロード (ファイル パスは予めバッファーに入れておく)
  2. GetProcAddress でエクスポート関数のアドレスをゲット (DllMain には何も書かなくてよい)
  3. 関数を単純に call で実行
  4. FreeLibrary で DLL をアンロード
  5. ExitThread のアドレスを push して VirtualFree に jmp

というわけで書いたコードがこれ↓

https://github.com/msmania/procjack/tree/1.0

メインのインジェクターは、pj.exe で、これに ターゲットの PID とインジェクトしたい DLL、そして実行したいエクスポート関数の序数を指定すると、ターゲットの中でコードが実行されます。実行の様子はこんな感じ。

Capture

シェルコードをデバッグしたい場合は、ターゲット側でスレッド作成時に例外を捕捉するようにしておくと、CreateRemoteThread が実行された時点でブレークしてくれて便利です。こんな感じ。

02

前述の通り、シェルコードは予め C で書いて expeb.exe としてコンパイルしてからアセンブリを整形しました。したがって、expeb のロジック自体は windows.h をインクルードしなくても動きます。Visual C++ だけでなく clang と gcc でもコンパイルして、もっとも効率の良いアセンブリを使おうと考えたのですが、結局 VC++ のアセンブリに落ち着きました。clang あたりがトリッキーなアセンブリを生成してくれるかと期待したのですが、どれも大差のないもので、最後は呼び出し規約の関係で VC++ に軍配が上がった感じです。長さは 1000 バイト前後です。手で頑張ればもう少し短くできそうな気はします。

試していませんが、Windows XP や 2000 でも動くはずです。少なくとも expeb.exe を Windows XP で動かして関数アドレスをとってくるところは問題ありませんでした。

ターゲットが AppContainer プロセスの時にも対応させるため、インジェクトする DLL のアクセス権をチェックして、"APPLICATION PACKAGE AUTHORITY\ALL APPLICATION PACKAGES" (SID=S-1-15-2-1) に対して読み取りと実行権限を割り当てています。実はこっちのコードを書く方が面倒だった・・・。Low プロセス用の権限を追加し忘れたので、Low だと動かないかも・・そのうち追加して更新します。

これで当初の目的は達成できた、と思いきや、実は一点だけ実現できていないことがあります。というのも、Wow64 のプロセスから Win64 のプロセスに対して CreateRemoteThread を実行すると、ERROR_ACCESS_DENIED で失敗してスレッドを作れないのです。VirtualAllocEx や WriteProcessMemory は問題ないのですが。逆の、Win64 から Wow64 への CreateRemoteThread は問題ありません。次のブログでいろいろ考察しているのですが、ちょっと時間がなくちゃんと読めていません。何かうまい方法があると思っているのですが。

DLL Injection and WoW64
http://www.corsix.org/content/dll-injection-and-wow64

最後にふと思い出したのが、知る人ぞ知るやねうらお氏の不真面目なほうのプロフィール。Reflective programming というより、やっていることはこっちに近いような。

やねうらおプロフィール
http://bm98.yaneu.com/bickle/profile.html

メインルーチンをオールアセンブラで組んだ、縦スクロールシューティングゲームを作成。創刊当時のマイコンBASICマガジンに投稿。BASICの部分は、16進ダンプをreadしてpokeしたのち、それを実行しているだけというBASICマガジンをナメ切った自慢の作品。当然のごとく、ボツにされる。

これでようやく小学校五年生の頃のやねうらお氏に追いついた!かもしれない。

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

[Win32] [Asm] Race condition between bit fields

久々にプログラミング ネタを投稿します。

サーバー系のソフトウェアが何らかのトラブルを引き起こした際、その原因がスレッド間の処理の競合で、現象の再現に苦労することがよくあります。race condition や timing issue と呼ばれる現象には非常に苦労させられます。最近の仕事で race condition に遭遇したのですが、ユーザーモードの単純なプログラムを書いて同じ現象を観察することができたので、まとめてみます。

まず、プログラムを書きます。ファイル 1 つです。

//
// 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

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;
    WORD Field1:1;
    WORD Field2:1;
    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;
            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;
            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 ) {
            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;
}

簡単なマルチスレッド プログラムです。ChurningThread がメイン スレッドから実行されるワーカー スレッドで、ThreadIndex の値によって以下 3 種類の振る舞いを行なうことができます。

  • グローバル変数 g_FlipFlop をひたすら反転
  • g_Target.Field1 と g_Field1 に g_FlipFlop を代入
  • g_Target.Field2 と g_Field2 に g_FlipFlop を代入

これを x64 ネイティブのプログラムにして実行します。手元の環境で 4  回ほど実行した結果を貼ります。

  • OS: Windows 8.1 x64
  • IDE: Visual Studio 2012
  • CPU: Intel Core i5-2520M (2 Cores, 4 Logical Processors)
  • Build: x64 Release

D:\VSDev\Projects\win32c>x64\Release\win32c 3 1000
[ChurningThread.29d4] 98: g_Target.Field2=0 g_Field2=1
[ChurningThread.29d4] 845: g_Target.Field2=0 g_Field2=1

D:\VSDev\Projects\win32c>x64\Release\win32c 3 1000
[ChurningThread.2ab0] 543: g_Target.Field2=0 g_Field2=1
[ChurningThread.2ab0] 581: g_Target.Field2=0 g_Field2=1
[ChurningThread.0154] 933: g_Target.Field1=0 g_Field1=1

D:\VSDev\Projects\win32c>x64\Release\win32c 3 1000

D:\VSDev\Projects\win32c>x64\Release\win32c 3 1000
[ChurningThread.0460] 83: g_Target.Field1=0 g_Field1=1
[ChurningThread.2088] 714: g_Target.Field2=1 g_Field2=0
[ChurningThread.0460] 803: g_Target.Field1=0 g_Field1=1

C 言語的にはこれはおかしな結果です。ChurningThread の処理を見る限りでは、g_Target.Field1 と g_Field1、g_Target.Field2 と g_Field2 の値が異なることはあり得ないはずです。というのも、ログを表示した後の処理で、どちらの値にも g_FlipFlop が代入されるはずだからです。ThreadIndex の値は途中で変更されないので、各スレッドは同じ処理をひたすら繰り返しているだけです。なぜ値が異なるのでしょう。g_FlipFlop の値も同時に反転し続けています。しかし、各スレッドは g_FlipFlop の値は一回読み取るだけで、g_Field1 には g_Target.Field1 の値を代入しているので、仮にこの 2 行の間に g_FlipFlop が反転したとしても、影響はないはずです。

この記事のタイトルや関数名からして、ビット フィールドが怪しいとお気づきになる方は多いと思います。正解です。TARGET::Field1 か TARGET::Field2 の片方を独立したメンバーにするだけでこの現象は解消します。では、なぜこのようなことが起こっていたのかをアセンブラで見てみます。

ChurningThread 関数全体のアセンブラは以下の通りです。ビットフィールドに関連するところは、g_Target.Field1 と g_Target.Field2 に値を代入しているところなので、該当箇所を青字にしました。

win32c!ChurningThread [d:\vsdev\projects\win32c\src\main.cpp @ 42]:
   42 00007ff6`d0471000 4889742410      mov     qword ptr [rsp+10h],rsi
   42 00007ff6`d0471005 57              push    rdi
   42 00007ff6`d0471006 4883ec50        sub     rsp,50h
   45 00007ff6`d047100a 33f6            xor     esi,esi
   45 00007ff6`d047100c 488bf9          mov     rdi,rcx
   45 00007ff6`d047100f 397104          cmp     dword ptr [rcx+4],esi
   45 00007ff6`d0471012 0f8e67010000    jle     win32c!ChurningThread+0x17f (00007ff6`d047117f)

win32c!ChurningThread+0x18 [d:\vsdev\projects\win32c\src\main.cpp @ 45]:
   45 00007ff6`d0471018 0f29742440      movaps  xmmword ptr [rsp+40h],xmm6
   45 00007ff6`d047101d f20f103513130000 movsd   xmm6,mmword ptr [win32c!_real (00007ff6`d0472338)]
   45 00007ff6`d0471025 0f297c2430      movaps  xmmword ptr [rsp+30h],xmm7
   45 00007ff6`d047102a f20f103dfe120000 movsd   xmm7,mmword ptr [win32c!_real (00007ff6`d0472330)]
   45 00007ff6`d0471032 48895c2460      mov     qword ptr [rsp+60h],rbx
   45 00007ff6`d0471037 660f1f840000000000 nop   word ptr [rax+rax]

win32c!ChurningThread+0x40 [d:\vsdev\projects\win32c\src\main.cpp @ 46]:
   46 00007ff6`d0471040 8b4f08          mov     ecx,dword ptr [rdi+8]
   46 00007ff6`d0471043 85c9            test    ecx,ecx
   46 00007ff6`d0471045 0f84e1000000    je      win32c!ChurningThread+0x12c (00007ff6`d047112c)

win32c!ChurningThread+0x4b [d:\vsdev\projects\win32c\src\main.cpp @ 46]:
   46 00007ff6`d047104b ffc9            dec     ecx
   46 00007ff6`d047104d 7476            je      win32c!ChurningThread+0xc5 (00007ff6`d04710c5)

win32c!ChurningThread+0x4f [d:\vsdev\projects\win32c\src\main.cpp @ 46]:
   46 00007ff6`d047104f ffc9            dec     ecx
   46 00007ff6`d0471051 0f85e6000000    jne     win32c!ChurningThread+0x13d (00007ff6`d047113d)

win32c!ChurningThread+0x57 [d:\vsdev\projects\win32c\src\main.cpp @ 62]:
   62 00007ff6`d0471057 8b1d8f250000    mov     ebx,dword ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)]
   62 00007ff6`d047105d d1eb            shr     ebx,1
   62 00007ff6`d047105f 83e301          and     ebx,1
   62 00007ff6`d0471062 3b1db41f0000    cmp     ebx,dword ptr [win32c!g_Field2 (00007ff6`d047301c)]
   62 00007ff6`d0471068 7426            je      win32c!ChurningThread+0x90 (00007ff6`d0471090)

win32c!ChurningThread+0x6a [d:\vsdev\projects\win32c\src\main.cpp @ 66]:
   66 00007ff6`d047106a ff15b80f0000    call    qword ptr [win32c!_imp_GetCurrentThreadId (00007ff6`d0472028)]
   66 00007ff6`d0471070 448b470c        mov     r8d,dword ptr [rdi+0Ch]
   66 00007ff6`d0471074 488d0d15120000  lea     rcx,[win32c!`string’ (00007ff6`d0472290)]
   66 00007ff6`d047107b 8bd0            mov     edx,eax
   66 00007ff6`d047107d 8b05991f0000    mov     eax,dword ptr [win32c!g_Field2 (00007ff6`d047301c)]
   66 00007ff6`d0471083 448bcb          mov     r9d,ebx
   66 00007ff6`d0471086 89442420        mov     dword ptr [rsp+20h],eax
   66 00007ff6`d047108a ff15d0100000    call    qword ptr [win32c!_imp_wprintf (00007ff6`d0472160)]

win32c!ChurningThread+0x90 [d:\vsdev\projects\win32c\src\main.cpp @ 68]:
   68 00007ff6`d0471090 0fb70555250000  movzx   eax,word ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)]
   68 00007ff6`d0471097 0fb70d861f0000  movzx   ecx,word ptr [win32c!g_FlipFlop (00007ff6`d0473024)]
   68 00007ff6`d047109e 6603c9          add     cx,cx
   68 00007ff6`d04710a1 6633c8          xor     cx,ax
   68 00007ff6`d04710a4 6683e102        and     cx,2
   68 00007ff6`d04710a8 6633c1          xor     ax,cx
   68 00007ff6`d04710ab 6689053a250000  mov     word ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)],ax

   69 00007ff6`d04710b2 8b0534250000    mov     eax,dword ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)]
   69 00007ff6`d04710b8 d1e8            shr     eax,1
   69 00007ff6`d04710ba 83e001          and     eax,1
   69 00007ff6`d04710bd 8905591f0000    mov     dword ptr [win32c!g_Field2 (00007ff6`d047301c)],eax
   70 00007ff6`d04710c3 eb78            jmp     win32c!ChurningThread+0x13d (00007ff6`d047113d)

win32c!ChurningThread+0xc5 [d:\vsdev\projects\win32c\src\main.cpp @ 52]:
   52 00007ff6`d04710c5 8b1d21250000    mov     ebx,dword ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)]
   52 00007ff6`d04710cb 83e301          and     ebx,1
   52 00007ff6`d04710ce 3b1d4c1f0000    cmp     ebx,dword ptr [win32c!g_Field1 (00007ff6`d0473020)]
   52 00007ff6`d04710d4 7426            je      win32c!ChurningThread+0xfc (00007ff6`d04710fc)

win32c!ChurningThread+0xd6 [d:\vsdev\projects\win32c\src\main.cpp @ 56]:
   56 00007ff6`d04710d6 ff154c0f0000    call    qword ptr [win32c!_imp_GetCurrentThreadId (00007ff6`d0472028)]
   56 00007ff6`d04710dc 448b470c        mov     r8d,dword ptr [rdi+0Ch]
   56 00007ff6`d04710e0 488d0d29110000  lea     rcx,[win32c!`string’ (00007ff6`d0472210)]
   56 00007ff6`d04710e7 8bd0            mov     edx,eax
   56 00007ff6`d04710e9 8b05311f0000    mov     eax,dword ptr [win32c!g_Field1 (00007ff6`d0473020)]
   56 00007ff6`d04710ef 448bcb          mov     r9d,ebx
   56 00007ff6`d04710f2 89442420        mov     dword ptr [rsp+20h],eax
   56 00007ff6`d04710f6 ff1564100000    call    qword ptr [win32c!_imp_wprintf (00007ff6`d0472160)]

win32c!ChurningThread+0xfc [d:\vsdev\projects\win32c\src\main.cpp @ 58]:
   58 00007ff6`d04710fc 0fb705e9240000  movzx   eax,word ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)]
   58 00007ff6`d0471103 0fb70d1a1f0000  movzx   ecx,word ptr [win32c!g_FlipFlop (00007ff6`d0473024)]
   58 00007ff6`d047110a 6633c8          xor     cx,ax
   58 00007ff6`d047110d 6683e101        and     cx,1
   58 00007ff6`d0471111 6633c1          xor     ax,cx
   58 00007ff6`d0471114 668905d1240000  mov     word ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)],ax

   59 00007ff6`d047111b 8b05cb240000    mov     eax,dword ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)]
   59 00007ff6`d0471121 83e001          and     eax,1
   59 00007ff6`d0471124 8905f61e0000    mov     dword ptr [win32c!g_Field1 (00007ff6`d0473020)],eax
   60 00007ff6`d047112a eb11            jmp     win32c!ChurningThread+0x13d (00007ff6`d047113d)

win32c!ChurningThread+0x12c [d:\vsdev\projects\win32c\src\main.cpp @ 49]:
   49 00007ff6`d047112c 33c0            xor     eax,eax
   49 00007ff6`d047112e 3905f01e0000    cmp     dword ptr [win32c!g_FlipFlop (00007ff6`d0473024)],eax
   49 00007ff6`d0471134 0f94c0          sete    al
   49 00007ff6`d0471137 8905e71e0000    mov     dword ptr [win32c!g_FlipFlop (00007ff6`d0473024)],eax

win32c!ChurningThread+0x13d [d:\vsdev\projects\win32c\src\main.cpp @ 73]:
   73 00007ff6`d047113d 488bcf          mov     rcx,rdi
   73 00007ff6`d0471140 ff15b2240000    call    qword ptr [win32c!RtlRandom (00007ff6`d04735f8)]
   73 00007ff6`d0471146 0f57c0          xorps   xmm0,xmm0
   73 00007ff6`d0471149 8bc0            mov     eax,eax
   73 00007ff6`d047114b f2480f2ac0      cvtsi2sd xmm0,rax
   73 00007ff6`d0471150 f20f5ec6        divsd   xmm0,xmm6
   73 00007ff6`d0471154 f20f59c7        mulsd   xmm0,xmm7
   73 00007ff6`d0471158 f20f2cc8        cvttsd2si ecx,xmm0
   74 00007ff6`d047115c ff15ae0e0000    call    qword ptr [win32c!_imp_Sleep (00007ff6`d0472010)]
   74 00007ff6`d0471162 ff470c          inc     dword ptr [rdi+0Ch]
   74 00007ff6`d0471165 ffc6            inc     esi
   74 00007ff6`d0471167 3b7704          cmp     esi,dword ptr [rdi+4]
   74 00007ff6`d047116a 0f8cd0feffff    jl      win32c!ChurningThread+0x40 (00007ff6`d0471040)

win32c!ChurningThread+0x170 [d:\vsdev\projects\win32c\src\main.cpp @ 74]:
   74 00007ff6`d0471170 0f287c2430      movaps  xmm7,xmmword ptr [rsp+30h]
   74 00007ff6`d0471175 0f28742440      movaps  xmm6,xmmword ptr [rsp+40h]
   74 00007ff6`d047117a 488b5c2460      mov     rbx,qword ptr [rsp+60h]

win32c!ChurningThread+0x17f [d:\vsdev\projects\win32c\src\main.cpp @ 77]:
   77 00007ff6`d047117f 33c0            xor     eax,eax
   78 00007ff6`d0471181 488b742468      mov     rsi,qword ptr [rsp+68h]
   78 00007ff6`d0471186 4883c450        add     rsp,50h
   78 00007ff6`d047118a 5f              pop     rdi
   78 00007ff6`d047118b c3              ret

よくある現象ですが、case ブロックの順番が逆転していますね。switch 文のコンパイル結果は気持ち悪いものです。それはさておき、C 言語では 1 行の処理である "g_Target.Field2 = g_FlipFlop" が、アセンブラだと 7 命令になっています。ビットフィールドの使用はパフォーマンス悪化の原因にもなりそうですね。

00007ff6`d0471090 0fb70555250000  movzx   eax,word ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)]
00007ff6`d0471097 0fb70d861f0000  movzx   ecx,word ptr [win32c!g_FlipFlop (00007ff6`d0473024)]
00007ff6`d047109e 6603c9          add     cx,cx
00007ff6`d04710a1 6633c8          xor     cx,ax
00007ff6`d04710a4 6683e102        and     cx,2
00007ff6`d04710a8 6633c1          xor     ax,cx
00007ff6`d04710ab 6689053a250000  mov     word ptr [win32c!g_Target+0x4 (00007ff6`d04735ec)],ax

特定のビットへの代入 (A=B) は、XOR を二回実行して

A = A^(B^A)

のように行われるようです。add と and は、効果を特定のビットに限定させている部分です。

この処理で問題なのは、赤字で示した xor と mov のところです。演算結果を ax レジスタに入れてから g_Target.Field2 に mov しています。この処理だと、代入したいビット以外のビットもメモリに送られてしまうことになります。00007ff6`d0471090 の処理の時は Field1 が 1 だったとして、00007ff6`d04710ab を実行するまでの間に別スレッドが Field1 を 0 に設定していたとしても、こっちのスレッドが Field2 を設定するときには ax レジスタに保存されていた古い Field1 も一緒に mov されるので、予期せずして Field1 が変更されることがありそうです。

これだけだと、コンパイラがお粗末でした、というだけで話が終わってしまいそうですが、実は続きがあります。今度は 32bit の x86 ネイティブでコンパイルして同じ 64bit Windows で実行してみます。

D:\VSDev\Projects\win32c>Release\win32c.exe 3 1000
[ChurningThread.275c] 851: g_Target.Field2=0 g_Field2=1

D:\VSDev\Projects\win32c>Release\win32c.exe 3 1000
[ChurningThread.2034] 40: g_Target.Field1=1 g_Field1=0
[ChurningThread.2034] 894: g_Target.Field1=0 g_Field1=1

D:\VSDev\Projects\win32c>Release\win32c.exe 3 1000

D:\VSDev\Projects\win32c>Release\win32c.exe 3 1000
[ChurningThread.2a28] 23: g_Target.Field2=1 g_Field2=0
[ChurningThread.2bd4] 874: g_Target.Field1=0 g_Field1=1

同じように競合が発生するようです。同じコードをコンパイルしているだけなので当たり前のように見えます。ここでもアセンブラを見てみます。全部貼ると長いので、抜粋します。

g_Target.Field2 = g_FlipFlop;

win32c!ChurningThread+0x36 [d:\vsdev\projects\win32c\src\main.cpp @ 62]:
   62 00161036 8b0d84331600    mov     ecx,dword ptr [win32c!g_Target+0x4 (00163384)]
   62 0016103c 8b1518301600    mov     edx,dword ptr [win32c!g_Field2 (00163018)]
   62 00161042 8bc1            mov     eax,ecx
   62 00161044 d1e8            shr     eax,1
   62 00161046 83e001          and     eax,1
   62 00161049 3bc2            cmp     eax,edx
   62 0016104b 741c            je      win32c!ChurningThread+0x69 (00161069)

win32c!ChurningThread+0x4d [d:\vsdev\projects\win32c\src\main.cpp @ 66]:
   66 0016104d 52              push    edx
   66 0016104e 50              push    eax
   66 0016104f ff760c          push    dword ptr [esi+0Ch]
   66 00161052 ff1514201600    call    dword ptr [win32c!_imp__GetCurrentThreadId (00162014)]
   66 00161058 50              push    eax
   66 00161059 68a8211600      push    offset win32c!`string’ (001621a8)
   66 0016105e ffd3            call    ebx
   66 00161060 8b0d84331600    mov     ecx,dword ptr [win32c!g_Target+0x4 (00163384)]
   66 00161066 83c414          add     esp,14h

win32c!ChurningThread+0x69 [d:\vsdev\projects\win32c\src\main.cpp @ 68]:
   68 00161069 a120301600      mov     eax,dword ptr [win32c!g_FlipFlop (00163020)]
   68 0016106e 03c0            add     eax,eax
   68 00161070 33c1            xor     eax,ecx
   68 00161072 83e002          and     eax,2
   68 00161075 66310584331600  xor     word ptr [win32c!g_Target+0x4 (00163384)],ax

   69 0016107c a184331600      mov     eax,dword ptr [win32c!g_Target+0x4 (00163384)]
   69 00161081 d1e8            shr     eax,1
   69 00161083 83e001          and     eax,1
   69 00161086 a318301600      mov     dword ptr [win32c!g_Field2 (00163018)],eax
   70 0016108b eb61            jmp     win32c!ChurningThread+0xee (001610ee)

g_Target.Field1 = g_FlipFlop;

win32c!ChurningThread+0x8d [d:\vsdev\projects\win32c\src\main.cpp @ 52]:
   52 0016108d 8b0d84331600    mov     ecx,dword ptr [win32c!g_Target+0x4 (00163384)]
   52 00161093 8b151c301600    mov     edx,dword ptr [win32c!g_Field1 (0016301c)]
   52 00161099 8bc1            mov     eax,ecx
   52 0016109b 83e001          and     eax,1
   52 0016109e 3bc2            cmp     eax,edx
   52 001610a0 741c            je      win32c!ChurningThread+0xbe (001610be)

win32c!ChurningThread+0xa2 [d:\vsdev\projects\win32c\src\main.cpp @ 56]:
   56 001610a2 52              push    edx
   56 001610a3 50              push    eax
   56 001610a4 ff760c          push    dword ptr [esi+0Ch]
   56 001610a7 ff1514201600    call    dword ptr [win32c!_imp__GetCurrentThreadId (00162014)]
   56 001610ad 50              push    eax
   56 001610ae 6830211600      push    offset win32c!`string’ (00162130)
   56 001610b3 ffd3            call    ebx
   56 001610b5 8b0d84331600    mov     ecx,dword ptr [win32c!g_Target+0x4 (00163384)]
   56 001610bb 83c414          add     esp,14h

win32c!ChurningThread+0xbe [d:\vsdev\projects\win32c\src\main.cpp @ 58]:
   58 001610be a120301600      mov     eax,dword ptr [win32c!g_FlipFlop (00163020)]
   58 001610c3 33c1            xor     eax,ecx
   58 001610c5 83e001          and     eax,1
   58 001610c8 66310584331600  xor     word ptr [win32c!g_Target+0x4 (00163384)],ax

   59 001610cf a184331600      mov     eax,dword ptr [win32c!g_Target+0x4 (00163384)]
   59 001610d4 83e001          and     eax,1
   59 001610d7 a31c301600      mov     dword ptr [win32c!g_Field1 (0016301c)],eax
   60 001610dc eb10            jmp     win32c!ChurningThread+0xee (001610ee)

2 回の XOR でビットの代入を行っているところは x64 と同じです。しかし、x64 で問題となっていた win32c!g_Target への mov による代入がありません。代わりに何をやっているかというと、win32c!g_Target に対して直接 XOR を実行しています。つまり、最初に win32c!g_Target の値を ecx に保存してから、最後に XOR でビットをセットするまでの間に g_Target が別スレッドによって変更されたとしても、g_Target に対して変更したい 1 ビットだけを XOR するので、他のビットへの影響はないと考えられます。より具体的に説明すると、xor の第二オペランドである ax レジスタは、その前に実行している and によって、設定対象外のビットが 0 になっているため、XOR しても変化しないはずなのです。理論的には。

実際に実行すると、x64 と同じく競合が発生します。そして、ビットフィールドではなく独立したメンバーにすると、競合は発生しません。まだ確証は持てていませんが、おそらく CPU キャッシュによるものと考えられます。CPU コア毎に存在している L1 キャッシュあたりに win32c!g_Target の値がキャッシュされていて、mov で取ってくるとき、もしくは xor で変更するときに、別コアで実行されているスレッドが変更した値がまだこちら側に来ていない、ということが起こっている可能性があります。さて、どうやって確かめたものか・・・。

シングル コアの CPU 上であれば、64bit プログラムだけで競合が発生し、32bit では競合が発生しないはずです。しかし、普通にプログラムを動かしただけでは、ちょうどいい場所でコンテキスト スイッチが起こらず、64bit プログラムでも競合は発生しません。デバッガーで無理やり競合させられるかどうかを試してみたいところです。

[2013/12/01] 続きを書きました。

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

[Win32] [x86 Assembler] Time Stamp Counter

久々にアセンブラ関連の記事を書きます。需要はあるのだろうか・・・

プログラムの中で、実行時間を計測したくなる場面は多々あります。そんなときはどんな API を使うでしょうか。パッと思いつくのは timeGetTime とか GetTickCount ですかね。GetSystemTime を使う人はあまりいないでしょう。QueryPerformanceCounter というのもあります。

timeGetTime 関数
http://msdn.microsoft.com/ja-jp/library/cc428795.aspx

GetTickCount 関数
http://msdn.microsoft.com/ja-jp/library/cc429827.aspx

GetSystemTime function
http://msdn.microsoft.com/en-us/library/ms724390(v=vs.85).aspx

QueryPerformanceCounter function
http://msdn.microsoft.com/en-us/library/ms644904(v=vs.85).aspx

どれを使ってもいいわけですが、とにかく厳密に測りたい場合や、一瞬で終わる処理を計測したい場合には、これらの API を使うと関数呼び出し時の時間のロスが無視できなくなります。もちろん、その分のロスを計算して結果から引くというのが普通ですが、アセンブラを使うという手も一応あります。

それが、RDTSC (=Read Time Stamp Counter) 命令です。詳細は IA-32 の仕様書に書いてありますが、RDTSC を実行すると、1 命令で Tick 値を取得することができます。しかも単位はクロック単位です。Pentium 以降の IA-32 アーキテクチャーでは、プロセッサーごとに TSC (=Time Stamp Counter) という 64bit カウンターが MSR (マシン固有レジスタ) に含まれており、RDTSC はこれを EDX:EAX レジスターにロードする命令です。

こんなプログラムを書いてみました。後でいろいろ遊ぶ伏線として、幾つかの関数を読んでいます。

なお、開発環境、実行環境は同じで、こんな感じです。

  • OS: Windows 7 SP1 (x64)
  • IDE: Visual Studio 2010 SP1
  • CPU: Core i3 530 2.93GHz (予算がないのだ)

//
// main.cpp
//

#include <Windows.h>
#include <stdio.h>

__int64 __fastcall rdtsc() {
    __asm {
        rdtsc
    }
}

__inline __int64 rdtsc_inline() {
    __asm {
        rdtsc
    }
}

void rdtsc_x86(long long int *ll) {
    __asm {
        rdtsc
        mov ecx, [ll]
        mov [ecx], eax
        mov [ecx+4], edx
    }
}

int wmain(int argc, wchar_t *argv[]) {
    if ( argc<2 )
        return ERROR_INVALID_PARAMETER;
   
    LARGE_INTEGER ll, ll1, ll2, ll3;

    wprintf(L"—–\n");

    DWORD wait= _wtoi(argv[1]);
    while (1) {
        QueryPerformanceCounter(&ll);
        ll1.QuadPart= rdtsc();
        ll2.QuadPart= rdtsc_inline();
        rdtsc_x86((long long*)&ll3);

        wprintf(L"QPC:  0x%08x`%08x\n", ll.HighPart, ll.LowPart);
        wprintf(L"ASM1: 0x%08x`%08x\n", ll1.HighPart, ll1.LowPart);
        wprintf(L"ASM2: 0x%08x`%08x\n", ll2.HighPart, ll2.LowPart);
        wprintf(L"ASM3: 0x%08x`%08x\n", ll3.HighPart, ll3.LowPart);
   
        wprintf(L"–\n");
        Sleep(wait);
    }

    return 0;
}

実行すると、こんな感じです。

E:\Visual Studio 2010\Projects\asmtest\Release> asmtest 1000
—–
QPC:  0x0000000a`cdfd9d44
ASM1: 0x00002b37`f6751321
ASM2: 0x00002b37`f675135e
ASM3: 0x00002b37`f6751394

QPC:  0x0000000a`ce28d20e
ASM1: 0x00002b38`a3483a0d
ASM2: 0x00002b38`a3483a4a
ASM3: 0x00002b38`a3483a80

QPC:  0x0000000a`ce54577b
ASM1: 0x00002b39`515df112
ASM2: 0x00002b39`515df142
ASM3: 0x00002b39`515df172

QPC:  0x0000000a`ce802c82
ASM1: 0x00002b3a`00b20afe
ASM2: 0x00002b3a`00b20b2e
ASM3: 0x00002b3a`00b20b5e

ASM1 の結果に絞って間隔を計算すると、ACD326EC, AE15B705, AF5419EC となり、平均値は AE14529F = 2,920,567,455 となります。プロセッサーのクロックが 2.93GHz なので、RDTSC は確かにクロック単位の値を取得しています。

サンプルでは 3 つの関数を書きました。

  • rdtsc ・・・ __fastcall 呼び出し規約
  • rdtsc_inline ・・・ __inline でインライン展開
  • rdtsc_x86 ・・・ パラメーター渡し

ソースコードを既定の Release ビルド設定でビルドすると、rdtsc_inline だけでなく rdtsc_x86 もインライン展開されます。rdtsc に __fastcall をつけたのはインライン展開を防ぐためで、__stdcall や __cdecl では展開されてしまいます。

コンパイルされた関数のアセンブラを見てみます。

0:000> uf asmtest!rdtsc
asmtest!rdtsc [e:\visual studio 2010\projects\asmtest\main.cpp @ 9]:
    9 011e1000 0f31            rdtsc
   13 011e1002 c3              ret

0:000> uf asmtest!wmain
asmtest!wmain [e:\visual studio 2010\projects\asmtest\main.cpp @ 30]:
   30 011e1010 55              push    ebp
   30 011e1011 8bec            mov     ebp,esp
   30 011e1013 83e4f8          and     esp,0FFFFFFF8h
   30 011e1016 83ec2c          sub     esp,2Ch
   31 011e1019 837d0802        cmp     dword ptr [ebp+8],2
   31 011e101d 53              push    ebx
   31 011e101e 56              push    esi
   31 011e101f 57              push    edi
   31 011e1020 7d0c            jge     asmtest!wmain+0x1e (011e102e)

asmtest!wmain+0x12 [e:\visual studio 2010\projects\asmtest\main.cpp @ 55]:
   55 011e1022 5f              pop     edi
   55 011e1023 5e              pop     esi
   55 011e1024 b857000000      mov     eax,57h
   55 011e1029 5b              pop     ebx
   55 011e102a 8be5            mov     esp,ebp
   55 011e102c 5d              pop     ebp
   55 011e102d c3              ret

asmtest!wmain+0x1e [e:\visual studio 2010\projects\asmtest\main.cpp @ 36]:
   36 011e102e 8b359c201e01    mov     esi,dword ptr [asmtest!_imp__wprintf (011e209c)]
   36 011e1034 68f4201e01      push    offset asmtest!`string’ (011e20f4)
   36 011e1039 ffd6            call    esi
   38 011e103b 8b450c          mov     eax,dword ptr [ebp+0Ch]
   38 011e103e 8b4804          mov     ecx,dword ptr [eax+4]
   38 011e1041 51              push    ecx
   38 011e1042 ff15a0201e01    call    dword ptr [asmtest!_imp___wtoi (011e20a0)]
   38 011e1048 83c408          add     esp,8
   38 011e104b 89442414        mov     dword ptr [esp+14h],eax
   38 011e104f 90              nop

asmtest!wmain+0x40 [e:\visual studio 2010\projects\asmtest\main.cpp @ 40]:
   40 011e1050 8d542418        lea     edx,[esp+18h]
   40 011e1054 52              push    edx
   40 011e1055 ff1500201e01    call    dword ptr [asmtest!_imp__QueryPerformanceCounter (011e2000)]
   41 011e105b e8a0ffffff      call    asmtest!rdtsc (011e1000)
   41 011e1060 8bd8            mov     ebx,eax
   41 011e1062 8954242c        mov     dword ptr [esp+2Ch],edx
   42 011e1066 0f31            rdtsc
   42 011e1068 8bf8            mov     edi,eax
   43 011e106a 8d442420        lea     eax,[esp+20h]
   43 011e106e 89542434        mov     dword ptr [esp+34h],edx
   43 011e1072 89442410        mov     dword ptr [esp+10h],eax

   43 011e1076 0f31            rdtsc
   43 011e1078 8b4c2410        mov     ecx,dword ptr [esp+10h]
   43 011e107c 8901            mov     dword ptr [ecx],eax
   43 011e107e 895104          mov     dword ptr [ecx+4],edx
   45 011e1081 8b4c2418        mov     ecx,dword ptr [esp+18h]
   45 011e1085 8b54241c        mov     edx,dword ptr [esp+1Ch]
   45 011e1089 51              push    ecx
   45 011e108a 52              push    edx
   45 011e108b 6804211e01      push    offset asmtest!`string’ (011e2104)
   45 011e1090 ffd6            call    esi
   46 011e1092 8b442438        mov     eax,dword ptr [esp+38h]
   46 011e1096 53              push    ebx
   46 011e1097 50              push    eax
   46 011e1098 682c211e01      push    offset asmtest!`string’ (011e212c)
   46 011e109d ffd6            call    esi
   47 011e109f 8b4c244c        mov     ecx,dword ptr [esp+4Ch]
   47 011e10a3 57              push    edi
   47 011e10a4 51              push    ecx
   47 011e10a5 6854211e01      push    offset asmtest!`string’ (011e2154)
   47 011e10aa ffd6            call    esi
   48 011e10ac 8b542444        mov     edx,dword ptr [esp+44h]
   48 011e10b0 8b442448        mov     eax,dword ptr [esp+48h]
   48 011e10b4 52              push    edx
   48 011e10b5 50              push    eax
   48 011e10b6 687c211e01      push    offset asmtest!`string’ (011e217c)
   48 011e10bb ffd6            call    esi
   50 011e10bd 68a4211e01      push    offset asmtest!`string’ (011e21a4)
   50 011e10c2 ffd6            call    esi
   51 011e10c4 8b4c2448        mov     ecx,dword ptr [esp+48h]
   51 011e10c8 83c434          add     esp,34h
   51 011e10cb 51              push    ecx
   51 011e10cc ff1504201e01    call    dword ptr [asmtest!_imp__Sleep (011e2004)]
   52 011e10d2 e979ffffff      jmp     asmtest!wmain+0x40 (011e1050)

関数 rdtsc は、RDTSC を実行するだけの関数になっています。インライン展開された関数は茶色と紫色で示しています。戻り値が EDX:EAX であることが考慮されて、うまく動くようになっています。edx レジスタが考慮されないのかと予想していましたが、インライン展開されても 64bit の戻り値に影響はないようです。

さて、次に QueryPerformanceCounter に注目してみます。上述の MSDN の説明を見ると、こんな注意書きがあります。

On a multiprocessor computer, it should not matter which processor is called. However, you can get different results on different processors due to bugs in the basic input/output system (BIOS) or the hardware abstraction layer (HAL). To specify processor affinity for a thread, use the SetThreadAffinityMask function.

「マルチ プロセッサーでも使えますよ。でも BIOS や HAL にバグがあるとプロセッサー毎に異なる結果が返ってくることがありますよ。」 ということです。BIOS や HAL のバグって言われても・・・既知のバグなら直しとけよ、としか言いようがありません。QueryPerformanceCounter を使うときは SetThreadAffinityMask を必ず使えってことなのでしょうか。微妙です。

少なくとも、QueryPerformanceCounter にはマルチプロセッサーを考慮した実装がなされていることが分かります。TSC カウンターはプロセッサー毎なので、先ほどの RDTSC 命令を呼び出す関数は、プロセッサー毎に異なる値を返します。よって、途中で割り込みが入って実行 CPU が変わることが予想される場合には使えません。

デバッグしていて気づきましたが、実は QueryPerformanceCounter は内部的に RDTSC を呼び出しています。これを確かめてみます。

0:000> x kernel32!QueryPerformanceCounter
76921732 kernel32!QueryPerformanceCounter = <no type information>
0:000> u 76921732
kernel32!QueryPerformanceCounter:
76921732 ff25d40d9276    jmp     dword ptr [kernel32!_imp__QueryPerformanceCounter (76920dd4)]
76921738 90              nop
76921739 90              nop
7692173a 90              nop
7692173b 90              nop
7692173c 90              nop
kernel32!IsDBCSLeadByte:
7692173d ff2568079276    jmp     dword ptr [kernel32!_imp__IsDBCSLeadByte (76920768)]
76921743 90              nop
0:000> dd 76920dd4 l1
76920dd4  775e8884
0:000> ln 775e8884
(775e8884)   ntdll!RtlQueryPerformanceCounter   |  (775e88e2)   ntdll!EtwEventEnabled
Exact matches:
    ntdll!RtlQueryPerformanceCounter = <no type information>

QueryPerformanceCounter は Kernel32.dll の関数ですが、これは単なるラッパーで、実体は ntdll.dll に実装されている RtlQueryPerformanceCounter であることが分かります。この関数のアセンブラを見てみます。

0:000> uf ntdll!RtlQueryPerformanceCounter
ntdll!RtlQueryPerformanceCounter:
775e8884 8bff            mov     edi,edi
775e8886 55              push    ebp
775e8887 8bec            mov     ebp,esp
775e8889 51              push    ecx
775e888a 51              push    ecx
775e888b f605ed02fe7f01  test    byte ptr [SharedUserData+0x2ed (7ffe02ed)],1
775e8892 0f840bf50400    je      ntdll!RtlQueryPerformanceCounter+0x55 (77637da3)

ntdll!RtlQueryPerformanceCounter+0x10:
775e8898 56              push    esi

ntdll!RtlQueryPerformanceCounter+0x11:
775e8899 8b0db803fe7f    mov     ecx,dword ptr [SharedUserData+0x3b8 (7ffe03b8)]
775e889f 8b35bc03fe7f    mov     esi,dword ptr [SharedUserData+0x3bc (7ffe03bc)]
775e88a5 a1b803fe7f      mov     eax,dword ptr [SharedUserData+0x3b8 (7ffe03b8)]
775e88aa 8b15bc03fe7f    mov     edx,dword ptr [SharedUserData+0x3bc (7ffe03bc)]
775e88b0 3bc8            cmp     ecx,eax
775e88b2 75e5            jne     ntdll!RtlQueryPerformanceCounter+0x11 (775e8899)

ntdll!RtlQueryPerformanceCounter+0x2c:
775e88b4 3bf2            cmp     esi,edx
775e88b6 75e1            jne     ntdll!RtlQueryPerformanceCounter+0x11 (775e8899)

ntdll!RtlQueryPerformanceCounter+0x30:
775e88b8 0f31            rdtsc
775e88ba 03c1            add     eax,ecx
775e88bc 0fb60ded02fe7f  movzx   ecx,byte ptr [SharedUserData+0x2ed (7ffe02ed)]
775e88c3 13d6            adc     edx,esi
775e88c5 c1e902          shr     ecx,2
775e88c8 e893ffffff      call    ntdll!_aullshr (775e8860)
775e88cd 8b4d08          mov     ecx,dword ptr [ebp+8]
775e88d0 8901            mov     dword ptr [ecx],eax
775e88d2 895104          mov     dword ptr [ecx+4],edx
775e88d5 5e              pop     esi

ntdll!RtlQueryPerformanceCounter+0x4e:
775e88d6 33c0            xor     eax,eax
775e88d8 40              inc     eax

ntdll!RtlQueryPerformanceCounter+0x51:
775e88d9 c9              leave
775e88da c20400          ret     4

ntdll!RtlQueryPerformanceCounter+0x55:
77637da3 8d45f8          lea     eax,[ebp-8]
77637da6 50              push    eax
77637da7 ff7508          push    dword ptr [ebp+8]
77637daa e8717ff9ff      call    ntdll!ZwQueryPerformanceCounter (775cfd20)
77637daf 85c0            test    eax,eax
77637db1 7d0d            jge     ntdll!RtlQueryPerformanceCounter+0x6f (77637dc0)

ntdll!RtlQueryPerformanceCounter+0x65:
77637db3 50              push    eax
77637db4 e89549fdff      call    ntdll!RtlSetLastWin32ErrorAndNtStatusFromNtStatus (7760c74e)

ntdll!RtlQueryPerformanceCounter+0x6b:
77637db9 33c0            xor     eax,eax
77637dbb e9190bfbff      jmp     ntdll!RtlQueryPerformanceCounter+0x51 (775e88d9)

ntdll!RtlQueryPerformanceCounter+0x6f:
77637dc0 837df800        cmp     dword ptr [ebp-8],0
77637dc4 0f850c0bfbff    jne     ntdll!RtlQueryPerformanceCounter+0x4e (775e88d6)

ntdll!RtlQueryPerformanceCounter+0x75:
77637dca 837dfc00        cmp     dword ptr [ebp-4],0
77637dce 0f85020bfbff    jne     ntdll!RtlQueryPerformanceCounter+0x4e (775e88d6)

ntdll!RtlQueryPerformanceCounter+0x7b:
77637dd4 6a78            push    78h
77637dd6 e814a5f9ff      call    ntdll!RtlSetLastWin32Error (775d22ef)
77637ddb ebdc            jmp     ntdll!RtlQueryPerformanceCounter+0x6b (77637db9)

RDTSC 命令がありました。さっきのサンプルプログラムでこの部分にブレークポイントを貼ると、確かに RDTSC が実行されていることが分かります。

0:002> bp 775e88b8
0:002> g
Breakpoint 0 hit
eax=00000000 ebx=14c34d78 ecx=00000000 edx=00000000 esi=00000000 edi=14c34da8
eip=775e88b8 esp=0045fe80 ebp=0045fe8c iopl=0         nv up ei pl zr na pe nc
cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00000246
ntdll!RtlQueryPerformanceCounter+0x30:
775e88b8 0f31            rdtsc
0:000> k
ChildEBP RetAddr
0045fe8c 00bb105b ntdll!RtlQueryPerformanceCounter+0x30
0045fecc 6a19263d asmtest!wmain+0x4b
0045ff18 7692339a MSVCR100!_initterm+0x13
0045ff24 775e9ed2 kernel32!BaseThreadInitThunk+0xe
0045ff64 775e9ea5 ntdll!__RtlUserThreadStart+0x70
0045ff7c 00000000 ntdll!_RtlUserThreadStart+0x1b

プログラムの実行結果を見ると分かりますが、QueryPerformanceCounter (以下 QPC と表記) と RDTSC の戻り値は全然違います。単位も異なっているようです。QPC の周波数は QueryPerformanceFrequency API で取得することができます。この環境で調べてみると、0x2BD8E6 = 2,852,116 となりました。クロックの 1/1000 ぐらいです。

QPC が RDTSC の値を元にしていることは確認できているので、何らかの計算をして周波数を調整していることになります。それが RtlQueryPerformanceCounter のアセンブラに隠されています。RDTSC の後のアセンブラをもう一度よく見てみます。

ntdll!RtlQueryPerformanceCounter+0x30:
775e88b8 0f31            rdtsc
775e88ba 03c1            add     eax,ecx
775e88bc 0fb60ded02fe7f  movzx   ecx,byte ptr [SharedUserData+0x2ed (7ffe02ed)]
775e88c3 13d6            adc     edx,esi
775e88c5 c1e902          shr     ecx,2
775e88c8 e893ffffff      call    ntdll!_aullshr (775e8860)
775e88cd 8b4d08          mov     ecx,dword ptr [ebp+8]
775e88d0 8901            mov     dword ptr [ecx],eax
775e88d2 895104          mov     dword ptr [ecx+4],edx
775e88d5 5e              pop     esi

ntdll!RtlQueryPerformanceCounter+0x4e:
775e88d6 33c0            xor     eax,eax
775e88d8 40              inc     eax

ntdll!RtlQueryPerformanceCounter+0x51:
775e88d9 c9              leave
775e88da c20400          ret     4

_anullshr という関数が怪しいですね。これを見てみます。

0:000> uf ntdll!_aullshr
ntdll!_aullshr:
775e8860 80f940          cmp     cl,40h
775e8863 7315            jae     ntdll!_aullshr+0x1a (775e887a)

ntdll!_aullshr+0x5:
775e8865 80f920          cmp     cl,20h
775e8868 7306            jae     ntdll!_aullshr+0x10 (775e8870)

ntdll!_aullshr+0xa:
775e886a 0fadd0          shrd    eax,edx,cl
775e886d d3ea            shr     edx,cl
775e886f c3              ret

ntdll!_aullshr+0x10:
775e8870 8bc2            mov     eax,edx
775e8872 33d2            xor     edx,edx
775e8874 80e11f          and     cl,1Fh
775e8877 d3e8            shr     eax,cl
775e8879 c3              ret

ntdll!_aullshr+0x1a:
775e887a 33c0            xor     eax,eax
775e887c 33d2            xor     edx,edx
775e887e c3              ret

eax と edx をcl だけ右シフトしています。これで QPC の結果が小さくなるわけです。
では ECX レジスタはどこから来ていたでしょうか。

775e88bc 0fb60ded02fe7f  movzx   ecx,byte ptr [SharedUserData+0x2ed (7ffe02ed)]
775e88c3 13d6            adc     edx,esi
775e88c5 c1e902          shr     ecx,2
775e88c8 e893ffffff      call    ntdll!_aullshr (775e8860)

SharedUserData から来ています。これは共有ユーザーモードページと呼ばれるデータで、デバッガー コマンドの !kuser で概要を表示できます。詳しくはデバッガーのヘルプを参照して下さい。

0:000> !kuser
_KUSER_SHARED_DATA at 7ffe0000
TickCount:    fa00000 * 000000000011d55a (0:05:04:21.406)
TimeZone Id: 0
ImageNumber Range: [8664 .. 8664]
Crypto Exponent: 0
SystemRoot: ‘C:\Windows’

ここでちょっとしたトリックが必要になります。
実はユーザーモード側から _KUSER_SHARED_DATA 構造体を見ても、全メンバーを見ることができません。そこで、カーネル モードから見る必要があります。同じ環境で livekd を使った出力がこれです。

Microsoft Windows [Version 6.1.7601]
Copyright (c) 2009 Microsoft Corporation.  All rights reserved.

E:\Visual Studio 2010\Projects\asmtest\Release>livekd

LiveKd v5.0 – Execute kd/windbg on a live system
Sysinternals – http://www.sysinternals.com
Copyright (C) 2000-2010 Mark Russinovich and Ken Johnson

Launching c:\debuggers\amd64\kd.exe:

Microsoft (R) Windows Debugger Version 6.12.0002.633 AMD64
Copyright (c) Microsoft Corporation. All rights reserved.

Loading Dump File [C:\Windows\livekd.dmp]
Kernel Complete Dump File: Full address space is available

Comment: ‘LiveKD live system view’
Symbol search path is: srv*c:\websymbols*
http://msdl.microsoft.com/download/symbols
Executable search path is:
Windows 7 Kernel Version 7601 (Service Pack 1) MP (4 procs) Free x64
Product: WinNt, suite: TerminalServer SingleUserTS
Built by: 7601.17640.amd64fre.win7sp1_gdr.110622-1506
Machine Name:
Kernel base = 0xfffff800`03a63000 PsLoadedModuleList = 0xfffff800`03ca8670
Debug session time: Sun Feb 13 11:34:57.897 17420 (UTC + 9:00)
System Uptime: 0 days 5:44:06.294
Loading Kernel Symbols
………………………………………………………
……………………………………………………….
……………………………………
Loading User Symbols
…………
Loading unloaded module list
……..Unable to enumerate user-mode unloaded modules, NTSTATUS 0xC0000147
0: kd> !kuser
*** ERROR: Module load completed but symbols could not be loaded for LiveKdD.SYS
_KUSER_SHARED_DATA at fffff78000000000
TickCount:    fa00000 * 0000000000142992 (0:05:44:06.281)
TimeZone Id: 0
ImageNumber Range: [8664 .. 8664]
Crypto Exponent: 0
SystemRoot: ‘C:\Windows’
0: kd> dt _KUSER_SHARED_DATA fffff78000000000
ntdll!_KUSER_SHARED_DATA
   +0x000 TickCountLowDeprecated : 0
(省略)
   +0x2ed TscQpcData       : 0x29 ‘)’
   +0x2ed TscQpcEnabled    : 0y1
   +0x2ed TscQpcSpareFlag  : 0y0
   +0x2ed TscQpcShift      : 0y001010 (0xa)
   +0x2ee TscQpcPad        : [2]  ""
(省略)

ntdll!_aullshr に渡されていたデータは SharedUserData+0x2ed でした。+2ed のところには、TscQpc*** という、まさに TSC と QPC に関連した値が保存されていることが分かります。

_KUSER_SHARED_DATA は公開されている構造体なので、Windows Driver Kit  に含まれる ntddk.h で定義を確認することができます。それがこれです。

//
// The following byte is consumed by the user-mode performance counter
// routines to improve latency when the source is the processor’s cycle
// counter.
//

union {
    UCHAR TscQpcData;
    struct {
        UCHAR TscQpcEnabled   : 1;
        UCHAR TscQpcSpareFlag : 1;
        UCHAR TscQpcShift     : 6;
    } DUMMYSTRUCTNAME;
} DUMMYUNIONNAME;

ビットフィールドになっていて、3 つのフィールドがあります。名前から推測できてしまいますが、一応アセンブラで確認していきましょう。ntdll!RtlQueryPerformanceCounter において、ntdll!_aullshr を呼び出す前に shr ecx,2 という命令で 2 ビット右シフトさせます。これは何かというと、TscQpcData を 2 ビット右シフト、つまり、ビットフィールドの TscQpcShift を取得していることになります。で、カーネル デバッガーの出力結果を見るとこの値は TscQpcShift : 0y001010 (0xa) 、つまり 10 です。これで謎が解けました。

RDTSC の結果と QPC の結果が 1000 倍ぐらい違っていましたが、これは TscQpcShift  の値だけ右シフトした値、つまり 1024 倍異なっていたことになります。これで QPC の仕組みは大体分かりました。

もう一度 ntdll!RtlQueryPerformanceCounter のアセンブラに戻ります。ntdll!RtlQueryPerformanceCounter+0x51 の後に ret 命令があって、ここで RDTSC を右シフトした値を返して終わるわけですが、関数自体は続いています。これはいつ呼ばれるでしょうか。それが関数のアタマにある、この部分です。

775e888b f605ed02fe7f01  test    byte ptr [SharedUserData+0x2ed (7ffe02ed)],1
775e8892 0f840bf50400    je      ntdll!RtlQueryPerformanceCounter+0x55 (77637da3)

また SharedUserData の値を使っています。+2ed なので TscQpcData の値ですが、今度は最下位ビットを test 命令で調べています。つまり TscQpcEnabled です。これが 0 の場合は、RDTSC が使われずに、ntdll!ZwQueryPerformanceCounter が呼ばれることになります。つまりカーネル モードの関数が呼ばれます。この関数が何を使っているのかについては、ここでは触れません。