yutopp's blog

サンドバッグになりたい

LLVMのGC(ガベージコレクション)サポートを使ってみる - Aizu Advent Calendar 2013(1日目)

Aizu Advent Calendar 2013、今年もやっていきます!宜しくお願いします。
一日目の @yutopp です。

今回は、日本語の資料が乏しいような気がする、LLVMのガベージコレクションサポートについてサラっと調べてみました。
ドキュメントは Accurate Garbage Collection with LLVM — LLVM 3.4 documentation になります。

実験には、Linux Mint 15(64bit)、Clang 3.4 svn(194075)、LLVM 3.4 svn(194075) を用いています。

ちなみに今回ガベージコレクション自体は実装していません申し訳 of the world

ガ・ベ・コ・レ、始まります

まずガベージコレクションについて。Wikipediaの記事を読むと良いです。
ガベージコレクション - Wikipedia

プログラムによって確保されたメモリ領域は、しっかり解放を行わないと闇に飲まれるので良くないのですが、頻繁にメモリ領域を確保するプログラムを書くと、それらをしっかり解放させるのは大変だったりします。
そこでガベージコレクションが登場します。ガベージコレクションはこの解放処理を自動で行なってくれるので、あるとそこそこ楽なわけです。

ガベージコレクションのアルゴリズムは色々な種類がありますが、大方ルートを辿るような動作をします。
ルートとは、メモリ領域を指し示す一番根本の部分のことを指します。大体複数存在します。
そして、このルートを辿っていくと、プログラム中で使われているメモリ領域が分かります。

例えば、C++で、ルートはスタックとレジスタとします。メモリ領域を指し示すポインタの値は、スタックやレジスタに配置されます。しかし、スタックなどにはポインタ以外の値(整数値)も配置されるため、ガベージコレクションを行う際に正しくポインタだけの値をたどる事ができません。

そこで、ポインタの値かどうか怪しいときは、その領域に触れない、または、その怪しい値もポインタの値とみなして生存判定をすることがあります。
このような振る舞いのガベージコレクションを”保守的なガベージコレクション”といいます。
そんな振る舞いのおかげで、プログラムは安全な方向に倒れます。(怪しいポインタや指すメモリ領域が勝手にいじられないため)
このガベージコレクションは、言語や処理系のサポートを必要としないのが利点で、実装もしやすいのですが、メモリリークなどが発生する場合あります。

一方で、ルート上の値がポインタかその他の値かを厳密に判別するガベージコレクションを”正確なガベージコレクション”といいます。
この厳密に判別のためには、言語処理系のサポートが欠かせないため、実装がややこしくなります。
また、処理系による実行時のサポートのため動作が遅くなることもあります。
しかし、全ての領域を正確に回収することができるので、まあこっちを使いたいですよね。

保守的なガベージコレクションであれば、LLVMなどのサポートは必要なく実装できる…。でもやっぱり正確なガベージコレクションを実装したい!
そこで、LLVMは、この正確なガベージコレクションを実装するためのサポートを提供してくれています。ヤッター!

正確なガベージコレクションのためのサポート

もう一度言いますが、ガベージコレクション自体は実装していません。つらい!
とりあえず、ガベージコレクションのサポートのテストをリポジトリに置いてみました。
yutopp/llvm-gc-support-test · GitHub

LLVMは、正確なガベージコレクションに必要なルート上のオブジェクトを判別するために、以下の方法を提供しています。

  • 組み込みのShadowStack実装
  • 独自のコード生成pluginの読み込み

ShadowStackは、汎用なスタック上の情報を記録するための手法だそうです。ポータブルな実装な分、オーバーヘッドが結構大きいとか書いてありましたが、見た感じそんなことなさそう…
このShadowStackは、LLVMの組み込みとあってデフォルトで利用できるため、手始めにはとても助かります。
ShadowStackのオーバーヘッドが気になるなど、別の手法の実装を使いたい場合は、自身でLLVMのGCサポート用のクラスをC++で実装し、LLVMに読み込ませることで拡張が可能です。

今回はShadowStackのみを利用してみます。

サンプルの説明

それぞれのディレクトリにコードが置いてあり、そのディレクトリで ./build をすれば、実行形式 a.out が生成されます。ア…windowsの方は自力でなんとかして下さい…

shadow_stack以下のファイルの説明です。

  • entry.cpp
    • main関数を定義してあります。この関数から、個々のサンプルのf()が呼び出されます。
  • llvm_shadow_stack.cpp
    • LLVMのドキュメントを参考にしたShadowStack用の定義です。
  • oreore_runtime.cpp
    • 俺々ランタイムです。なんちゃってメモリアロケータと、GCルートのクローラと、ちょっとした関数が込めてあります。

それぞれのtest_functionの先頭には、C++で書いたらこうなるかなーというコードが書かれています。

  • simple_function_call/test_function.ll
    • gc領域の関数呼び出しテスト
  • simple_nested_function_call/test_function.ll
    • ネストされたgc領域の関数呼び出しテスト
  • simple_nested_with_no_gc_function_call/test_function.ll
    • 途中に普通の領域の関数を挟んだ、ネストされたgc領域の関数呼び出しテスト
  • with_metadata/test_function.ll
    • ShadowStackを調べるのに使った残りファイル

それぞれの *_function_call では、ループをひたすら回す処理が書いてあり、その中で毎回int型のメモリを確保するmy_allocを呼んでいます。
そして、俺々ランタイムのなんちゃってメモリアロケータは、10個しかメモリ領域を管理できない出来損ないです。
なので、メモリを10回確保して開放しないでいると、11回目のメモリ確保でガベージコレクションがトリガされるようになっています。
実際に実行してみると、(多分)そのような挙動をしていることがわかります。

ガベージコレクションサポートを受けるには

まず関数に gc "name" の指定をつけます。"name" の 部分は使用するプラグインの名前になります。"shadow-stack" はデフォルトで使うことができます。
次に、GC管理下に置くポインタをおく領域を alloca にて作成し、@llvm.gcroot でマークを行います。
LLVMはmem2regの最適化によって、alloca で確保した領域もSSA形式に変換してしまう可能性があるので、マークを行う必要があります。
また、全ての @llvm.gcroot の呼び出しは、最初のBasicBlockで行われる必要があるようです。
@llvm.gcroot の 第1引数は必ずalloca命令かallocabitcastを参照する値でなければなりません。
第2引数には、ポインタに関連付けられたメタデータへのポインタが入りますが、このポインタは*必ず*定数もしくはglobalな値のアドレスである必要があります。利用しない場合はnullを渡せば良いようです。

リードバリアと、ライトバリアは、@llvm.gcread@llvm.gcwrite 組み込み命令で実現できます。

あとは、アロケータがガベージコレクションのトリガを引いた際に、ルートを巡ってガベージコレクションを行うなりなんなりするだけです。多分!

LLVM Language Reference Manual — LLVM 3.4 documentation
Accurate Garbage Collection with LLVM — LLVM 3.4 documentation


ShadowStackについて

自分がShadowStackについてよく分かっていなかったので、LLVMではどのように実装されているか見てみました。
組み込みのShadowStackを生成するプラグインのコードは LLVM: ShadowStackGC.cpp Source File にありました。
また、ここで出てくる型や変数の定義は Accurate Garbage Collection with LLVM — LLVM 3.4 documentation となります。

以下は、with_metadata/test_function.ll を -filetype=asm で llc に食わせた結果のアセンブリにコメントを加えたものです。

	.file	"test_function.ll"
	.text
	.globl	f
	.align	16, 0x90
	.type	f,@function
f:                                      # @f
	.cfi_startproc
# BB#0:                                 # %entry
# !!!!!!!!!!!!!!!!!!!!!!!!
# !!!! -> [1]
# !!!!!!!!!!!!!!!!!!!!!!!!
	mov	rax, qword ptr [rip + llvm_gc_root_chain]
	mov	qword ptr [rsp - 24], __gc_f
	mov	qword ptr [rsp - 16], 0
	mov	qword ptr [rsp - 32], rax
	lea	rax, qword ptr [rsp - 32]
	mov	qword ptr [rip + llvm_gc_root_chain], rax
	mov	qword ptr [rsp - 8], 0
# !!!!!!!!!!!!!!!!!!!!!!!!
# !!!! -> [2]
# !!!!!!!!!!!!!!!!!!!!!!!!
	mov	rax, qword ptr [rsp - 32]
	mov	qword ptr [rip + llvm_gc_root_chain], rax
	ret
.Ltmp0:
	.size	f, .Ltmp0-f
	.cfi_endproc

	.type	.Lstr.1,@object         # @str.1
	.section	.rodata.str1.16,"aMS",@progbits,1
	.align	16
.Lstr.1:
	.asciz	"How is your progress?"
	.size	.Lstr.1, 22

	.type	.Lstr.2,@object         # @str.2
	.section	.rodata.str1.1,"aMS",@progbits,1
.Lstr.2:
	.asciz	"Doudesuka?"
	.size	.Lstr.2, 11

	.type	llvm_gc_root_chain,@object # @llvm_gc_root_chain
	.section	.bss.llvm_gc_root_chain,"aGw",@nobits,llvm_gc_root_chain,comdat
	.weak	llvm_gc_root_chain
	.align	8
llvm_gc_root_chain:
	.quad	0
	.size	llvm_gc_root_chain, 8

	.type	__gc_f,@object          # @__gc_f
	.section	.rodata,"a",@progbits
	.align	16
# !!!!!!!!!!!!!!!!!!!!!!!!
# !!!! -> [3]
# !!!!!!!!!!!!!!!!!!!!!!!!
__gc_f:
	.long	2                       # 0x2
	.long	2                       # 0x2
	.quad	.Lstr.1
	.quad	.Lstr.2
	.size	__gc_f, 24


	.section	".note.GNU-stack","",@progbits

ビックリマークで囲んであるところが重要なところです。
[1] は、新しいStackEntryを生成し、新しいStackEntryへllvm_gc_root_chainのリストをつなぎ替える部分です。
この時点で、llvm_gc_root_chainに新しいスタックフレームのStackEntryへのアドレスが代入され、この新しいスタックフレームのStackEntryに古いllvm_gc_root_chainの値がコピーされます。
ここを抜けると、スタックの状態はこのようになっています。
f:id:yutopp:20131129145240p:plain
また、metadataをもつRootsが、配列の先頭に配置されるようになっているようです。

[2] は、llvm_gc_root_chainのリストを、このスタックフレームに入る前のものにつなぎ直す処理です。

[3] は、FrameMapという構造で、GCのセクションの分だけ生成されるようです。
f:id:yutopp:20131129145251p:plain

llvm_gc_root_chainは、このStackEntryをつなぐ単方向リストの先頭です。
よって、

for( StackEntry* entry=llvm_gc_root_chain; entry!=nullptr; entry=entry->Next ) {
    unsigned i = 0;

    // For roots [0, NumMeta), the metadata pointer is in the FrameMap.
    for( ;i < entry->Map->NumMeta; ++i ) {
        // entry->Roots[i] と entry->Map->Meta[i] で 各ルートとメタデータにアクセスできる
    }

    // For roots [NumMeta, NumRoots), the metadata pointer is null.
    for( ;i < entry->Map->NumRoots; ++i ) {
        // entry->Roots[i] で 各ルートにアクセスできる。メタデータは無し
    }
}

というコードで、スタック上のルートを巡ることができるようになりました!やりました!
でもマルチスレッド環境だと大変なことになりますねこれは…

おわりに

色々足りない感はありますが、ここで筆を置くことにします。
こう言い換えろ→論文に死んでも書いてはいけない言葉30 読書猿Classic: between / beyond readers

Boost.AsioやリンカやGCの実装についてはまた今度書きます!!!!!
さて、Aizu Advent Calendar 2013、2日目は Hiroyuki Sano さんです!宜しくおねがいします!!!!

LLVM3.3 と VS11 で遊んでみた

リンカが完成していなくても話題のLLVMで遊びたいってワケ

環境: Windows 7(x64),VS Express 2012 for Desktop,LLVM3.3

LLVMをビルドし,C++から呼んでIRを吐かせるまでの記事.自分用メモ.
サクサクとやりたいので自分でやってみた方法を書きます.ほとんどドキュメント通りです.

VSでインストールするまでのドキュメント
http://llvm.org/docs/GettingStartedVS.html

1. LLVM3.3をダウンロード
http://llvm.org/releases/download.html#3.3
LLVM source code というやつ
自分はD:に展開した.ので,D:\llvm-3.3.src に LLVM が配置されている.

2. CMakeする
http://www.cmake.org/cmake/resources/software.html
より最新の CMake を持ってくる.
GUI の CMake を開き,ソースコードとバイナリの出力先を LLVM の配置パス(D:\llvm-3.3.src)にする.
で,Configure."Visual Studio 11" と "Use default native compilers" を選択.で Finish.
(makeにPythonが使われているが,この際に Python3.3 が選ばれるとconfigureに失敗する.
http://stackoverflow.com/questions/13772617/building-llvm-fails-with-empty-error-message
ので,自分はインストールしていた Python3.3 をアンインストールして,Python 2.7.5 を入れた.つらい.)
終わったら Generate し,LLVM が配置されたディレクトリに移動.

3. ビルドする
LLVM が配置されたディレクトリに LLVM.sln というファイルが出来ているので開く.で,開いたそのままの状態でビルドを始める.今回は,Win32 の Debug ビルド.
すこし時間がかかるので,その間にツイッターをしましょう.

特にトラブルも起きなかったので無事ビルドは終わり.


使ってみるゾ
適当なプロジェクトを作り,
インクルードパスは,D:\llvm-3.3.src\include
ライブラリパスは,D:\llvm-3.3.src\lib\Debug
に通す.このプロジェクトも,Win32 の Debug でビルドする.

サンプルプログラム
http://www.ibm.com/developerworks/jp/opensource/library/os-createcompilerllvm1/
を参考(丸パクリ)にした.LLVM の IR をダンプする.
MSVC(v110)でコンパイルエラーが発生するので,プロジェクトのプロパティ -> C/C++ -> コマンドライン に -D_SCL_SECURE_NO_WARNINGS を追加しちゃって下さい.

#include <vector>
#include <string>
#include <iostream>

#include "llvm/ADT/ArrayRef.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/IRBuilder.h"


int main()
{
    llvm::LLVMContext& context = llvm::getGlobalContext();
    std::shared_ptr<llvm::Module> const module = std::make_shared<llvm::Module>( "Bunchou", context );
    llvm::IRBuilder<> builder( context );

    llvm::FunctionType* const func_type = llvm::FunctionType::get( builder.getVoidTy(), false );
    llvm::Function* const main_func =
        llvm::Function::Create( func_type, llvm::Function::ExternalLinkage, "main", module.get() );
    llvm::BasicBlock* const entry = llvm::BasicBlock::Create( context, "entrypoint", main_func );
    builder.SetInsertPoint( entry );

    llvm::Value* const sintyoku_doudesuka = builder.CreateGlobalStringPtr( "進捗どうですか?\n" );

    std::vector<llvm::Type*> puts_args;
    puts_args.push_back( builder.getInt8Ty()->getPointerTo() );
    llvm::ArrayRef<llvm::Type*> args_ref( puts_args );

    llvm::FunctionType* const puts_type =
        llvm::FunctionType::get( builder.getInt32Ty(), args_ref, false );
    llvm::Constant* const puts_func = module->getOrInsertFunction( "puts", puts_type );

    builder.CreateCall( puts_func, sintyoku_doudesuka );
    builder.CreateRetVoid();

    module->dump();

    // wait
    { char c; std::cin >> c; }
}


//
//
#pragma comment( lib, "LLVMXCoreCodeGen.lib" )
#pragma comment( lib, "LLVMTableGen.lib" )
#pragma comment( lib, "LLVMSystemZCodeGen.lib" )
#pragma comment( lib, "LLVMSparcCodeGen.lib" )
//#pragma comment( lib, "LLVMPTXCodeGen.lib" )
#pragma comment( lib, "LLVMPowerPCCodeGen.lib" )
#pragma comment( lib, "LLVMMSP430CodeGen.lib" )
#pragma comment( lib, "LLVMMipsCodeGen.lib" )
#pragma comment( lib, "LLVMMCJIT.lib" )
#pragma comment( lib, "LLVMRuntimeDyld.lib" )
#pragma comment( lib, "LLVMObject.lib" )
#pragma comment( lib, "LLVMMCDisassembler.lib" )
#pragma comment( lib, "LLVMXCoreDesc.lib" )
#pragma comment( lib, "LLVMXCoreInfo.lib" )
#pragma comment( lib, "LLVMSystemZDesc.lib" )
#pragma comment( lib, "LLVMSystemZInfo.lib" )
#pragma comment( lib, "LLVMSparcDesc.lib" )
#pragma comment( lib, "LLVMSparcInfo.lib" )
#pragma comment( lib, "LLVMPowerPCDesc.lib" )
#pragma comment( lib, "LLVMPowerPCInfo.lib" )
#pragma comment( lib, "LLVMPowerPCAsmPrinter.lib" )
//#pragma comment( lib, "LLVMPTXDesc.lib" )
//#pragma comment( lib, "LLVMPTXInfo.lib" )
//#pragma comment( lib, "LLVMPTXAsmPrinter.lib" )
#pragma comment( lib, "LLVMMipsDesc.lib" )
#pragma comment( lib, "LLVMMipsInfo.lib" )
#pragma comment( lib, "LLVMMipsAsmPrinter.lib" )
#pragma comment( lib, "LLVMMSP430Desc.lib" )
#pragma comment( lib, "LLVMMSP430Info.lib" )
#pragma comment( lib, "LLVMMSP430AsmPrinter.lib" )
#pragma comment( lib, "LLVMMBlazeDisassembler.lib" )
#pragma comment( lib, "LLVMMBlazeAsmParser.lib" )
#pragma comment( lib, "LLVMMBlazeCodeGen.lib" )
#pragma comment( lib, "LLVMMBlazeDesc.lib" )
#pragma comment( lib, "LLVMMBlazeAsmPrinter.lib" )
#pragma comment( lib, "LLVMMBlazeInfo.lib" )
#pragma comment( lib, "LLVMLinker.lib" )
#pragma comment( lib, "LLVMipo.lib" )
#pragma comment( lib, "LLVMInterpreter.lib" )
#pragma comment( lib, "LLVMInstrumentation.lib" )
#pragma comment( lib, "LLVMJIT.lib" )
#pragma comment( lib, "LLVMExecutionEngine.lib" )
#pragma comment( lib, "LLVMDebugInfo.lib" )
//#pragma comment( lib, "LLVMCppBackend.lib" )
//#pragma comment( lib, "LLVMCppBackendInfo.lib" )
//#pragma comment( lib, "LLVMCellSPUCodeGen.lib" )
//#pragma comment( lib, "LLVMCellSPUDesc.lib" )
//#pragma comment( lib, "LLVMCellSPUInfo.lib" )
//#pragma comment( lib, "LLVMCBackend.lib" )
//#pragma comment( lib, "LLVMCBackendInfo.lib" )
//#pragma comment( lib, "LLVMBlackfinCodeGen.lib" )
//#pragma comment( lib, "LLVMBlackfinDesc.lib" )
//#pragma comment( lib, "LLVMBlackfinInfo.lib" )
#pragma comment( lib, "LLVMBitWriter.lib" )
#pragma comment( lib, "LLVMX86Disassembler.lib" )
#pragma comment( lib, "LLVMX86AsmParser.lib" )
#pragma comment( lib, "LLVMX86CodeGen.lib" )
#pragma comment( lib, "LLVMX86Desc.lib" )
#pragma comment( lib, "LLVMX86AsmPrinter.lib" )
#pragma comment( lib, "LLVMX86Utils.lib" )
#pragma comment( lib, "LLVMX86Info.lib" )
#pragma comment( lib, "LLVMAsmParser.lib" )
#pragma comment( lib, "LLVMARMDisassembler.lib" )
#pragma comment( lib, "LLVMARMAsmParser.lib" )
#pragma comment( lib, "LLVMARMCodeGen.lib" )
#pragma comment( lib, "LLVMARMDesc.lib" )
#pragma comment( lib, "LLVMARMAsmPrinter.lib" )
#pragma comment( lib, "LLVMARMInfo.lib" )
#pragma comment( lib, "LLVMArchive.lib" )
#pragma comment( lib, "LLVMBitReader.lib" )
//#pragma comment( lib, "LLVMAlphaCodeGen.lib" )
#pragma comment( lib, "LLVMSelectionDAG.lib" )
#pragma comment( lib, "LLVMAsmPrinter.lib" )
#pragma comment( lib, "LLVMMCParser.lib" )
#pragma comment( lib, "LLVMCodeGen.lib" )
#pragma comment( lib, "LLVMScalarOpts.lib" )
#pragma comment( lib, "LLVMInstCombine.lib" )
#pragma comment( lib, "LLVMTransformUtils.lib" )
#pragma comment( lib, "LLVMipa.lib" )
#pragma comment( lib, "LLVMAnalysis.lib" )
#pragma comment( lib, "LLVMTarget.lib" )
#pragma comment( lib, "LLVMCore.lib" )
//#pragma comment( lib, "LLVMAlphaDesc.lib" )
//#pragma comment( lib, "LLVMAlphaInfo.lib" )
#pragma comment( lib, "LLVMMC.lib" )
#pragma comment( lib, "LLVMSupport.lib" )

実行すると,以下のようなIRが生成されます.

; ModuleID = 'Bunchou'

@0 = private unnamed_addr constant [18 x i8] c"\90i\92\BB\82\C7\82\A4\82\C5\82\B7\82\A9\81H\0A\00"

define void @main() {
entrypoint:
  %0 = call i32 @puts(i8* getelementptr inbounds ([18 x i8]* @0, i32 0, i32 0))
  ret void
}

declare i32 @puts(i8*)

ではでは,実行してみます.
LLVM を展開したディレクトリ(D:\llvm-3.3.src)の bin\Debug に lli.exe という物がある.これに生成したIRを食わせると実行してくれるようなのでやってみましょう.


f:id:yutopp:20130910001113p:plain

ヤッター,動きました!進捗ありました!


IRから実行形式にするには
http://stackoverflow.com/questions/13928250/how-to-save-ir-to-a-file-and-build-it-to-an-executable-file


さあ文鳥言語に組み込もうっと.

リンカ作ろうJP$1

おはようございます.Aizu Advent Calendar 1日目です!

リンカ作ろう,ということで,リンカを作っている最中にハマったことでもメモっていこうと思います.
間違いがありましたら是非教えて頂けると嬉しいです.

というか普通に間に合いませんでした.申し訳 of the world.
ひとまず,平凡なストレージクラスもつセクションを指すシンボルをリンクすることができます.
要するに,外部のライブラリをimportできません… 本当はputsで文字列を出力させたかったでござる.
現時点でどれ位かというと,この程度のコードをコンパイルしたオブジェクトしかリンクできません.ギョエー

    int hoge()
    {
        char const* const moji = "uhohoho";

        int length = 0;
        for( char const* p = moji; *p != '\0'; ++p ) {
            ++length;
        }

        return length;
    }

    int fuga()
    {
        return hoge();
    }

    int test_entry_point()
    {
        return fuga();
    }

環境は Windows 7(x64),Visual Studio 2012(MSVC v110)です.

リンカ is 何


(調子に乗った図)
コンパイラが生成したオブジェクトファイル(.oだったり.objだったり)は単体では実行できないので,
オブジェクトファイルと必要なライブラリの情報を上手いこと繋ぎあわせて,OSが認識できる形式に整えるものです.

ファイル形式

ライブラリやオブジェクトファイルを繋ぎ合わせるためには個々の情報を引っこ抜く必要があります.
また,そのためにはそれらのファイル形式に対応する必要があります.
今回は,Windowsで色々試していたので,COFF と PE について調べていました.

(仕様)
Microsoft PE and COFF Specification


ライブラリ(アーカイブ) 形式

名前の通り単純な構造で,ヘッダとオブジェクトファイルが連続で詰められている感じです.
一つのファイルが大きいことが多いので,効率良く読み込めるように工夫が必要だと思います.
ライブラリに含まれる関数などのシンボル名を列挙したアーカイブがあるのが素敵です.
個々のヘッダのデリミタが `\n と特徴的(?)なので,エディタでもかなり読みやすいです.
f:id:yutopp:20121130055624p:plain

(参考資料)
ar (UNIX) - Wikipedia
アレ用の何か
Microsoft PE and COFF Specification(6章)


インポートライブラリ 形式

上記の ライブラリ(アーカイブ) 形式 とよく似たフォーマットです.
インポートライブラリヘッダとnullで区切られたインポート名とDLL名が連続で詰められています.
long版 と short版 があります.Windows SDKに含まれる kernel32.lib などはこの形式の short版 のようです.
インポートライブラリヘッダの構造は WinNT.h の IMPORT_OBJECT_HEADER です.
ヘッダは COFF のファイルヘッダにめちゃくちゃ似てます. 気づかないとつらぽよになります.

(参考資料)
Microsoft PE and COFF Specification(7章)


ANON Object

こちらもヘッダが COFF のファイルヘッダにめちゃくちゃ似てる上に,実体もよく分かりません.滅んで欲しい.
バージョンによってヘッダの構造が変わります. WinNT.h では ANON_OBJECT_HEADER と ANON_OBJECT_HEADER_V2 ,ANON_OBJECT_HEADER_BIGOBJ です.
これも COFF のヘッダかと思いこんでひたすら悩みました.つらい.
コンパイラのオプションで生成しないようにできます.とりあえず今回は無視をキメました.

(参考資料)
c - Disassemble Microsoft Visual Studio 2003 compiler output - Stack Overflow


COFF 形式

本命.ライブラリの中に詰められているオブジェクトの形式のひとつです.拡張子は .obj や .o となります.
ファイルヘッダ,セクションヘッダ,セクション,シンボルテーブル,etc なシンプルな構造をしています.
ファイルヘッダ は WinNT.h の IMAGE_FILE_HEADER です.
先頭 2バイトが i386 用のものであることを表す 4C 01 であることが多い感じです.(IMAGE_FILE_HEADER の Machineメンバ が 0x014c)
セクション名には,お馴染みの .text だったり .data などの名前がついています.
.drectve という名前で,かつ IMAGE_SCN_LNK_INFO フラグの立っているセクションには,リンカへの情報が収められているので結構重要です.また,リンカはこの情報を実行形式には含めないようにしたほうが良いみたいです.
シンボルテーブルには,_foo などの関数名と,対応するセクションへの index などが収められています.
0-based の index と 1-based の index が混じっていたりで,注意しないと時間を持っていかれます(体験談)

リンカは,ここからシンボル情報を引っこ抜いて,セクションのデータを展開します.
セクションには再配置情報が含まれているので,そのストレージクラスなどを適切に処理しつつオブジェクトを配置していきます.(デキナカッタ…)

(参考資料)
アレ用の何か
目次(翻訳されたもの.ちょっと古い)


PE 形式

COFFから派生したフォーマットのよう.実行形式です.
DOS用のセクション,PEのヘッダ,セクションヘッダ,セクション…といった構造です.
こちらも PE32 と PE32+ で構造が変わります.PE32+ は 64bit 用に拡張されたものです.
今回はPE32を使いました.WinNT.h の IMAGE_NT_HEADERS と IMAGE_OPTIONAL_HEADER32 あたりがキモです.
重要なものは,IMAGE_OPTIONAL_HEADER32 の SectionAlignment と FileAlignment,加えてNT系だと SizeOfImage の値だと思います.
重要で無さそうな雰囲気を放っていますが,これらの値を正しく設定し,かつ正しく align されていないと実行すら出来ません.(デン!)
なので,吐いた実行形式が正しい形式でないと怒られるときは,一番初めにここを確認すると良いと思います.
SectionAlignment はメモリに展開されるときのアラインメントを指定します.
FileAlignment は実際のファイルに書き込むときのアラインメントです.
SizeOfImage は メモリに展開されるときの大きさを指定します.なので,SectionAlignment の倍数になります.(違うかも?)
後は実際にメモリに展開されるときのことを考えつつ,アドレスを配置していくと大体実行できる気がします.

(参考資料)
EXEファイルの内部構造(PEヘッダ) (1/3):CodeZine


ソースコード

fileformat: yutopp/ytl at develop · GitHub
linker : Dimnal/linker · GitHub
絶賛突貫工事中です.コードが汚いのは分かっています…分かっています…

linkerの動作として,

  1. lib と obj を食わせる
  2. エントリポイントのシンボルから配置していく
  3. 再配置情報に外部シンボル情報が含まれていた場合,読み込み済みの lib と obj から探し出し,配置する
    1. 無い場合 -> リンクエラー
  4. セクションのオフセット分をアドレスに足す
  5. PE 形式に込めて出力

といった感じです.
今はとりあえず動けば良い,な感じで書いています.

そして現在,IMAGE_SYM_CLASS_STATIC というストレージクラスを正しく処理できなくて詰んでます!ギョギョギョ
これが原因で,冒頭のようなコードしかリンクできません.うぅ.

そんなこんなで リンカ作ろうJP は現在進行形です.アドバイス下さい…!


まとめ(?)

"コンパイラを作っている方は多いし,じゃあリンカ書くか" な感じで始まったリンカ作りですが,結構面白いのでオススメです.
とりあえず今回は完成度がアレなのでリベンジしたいところです!ひとまず今回はここまで…


Aizu Advent Calendar 2日目は ___Johniel さんです.宜しくお願いします!
2日目 -> 82連鎖: 台湾に行きました。

読み方 of "セキュリティキャンプ2012に参加しました"

一つ前の記事で,セキュリティキャンプ2012についての感想文をexeに詰めて置いておいたのですが,そのままにしておくのも悲しいので,ザックリと解き方を書いておこうと思います.
未だに不慣れなので,変な箇所がありましたら是非教えて下さい><

先に,出てくる文章を貼っておきますね。

セキュリティキャンプ2012 ソフトウェア・セキュリティ・クラスに参加してきました!
とってもとっても楽しく、刺激的なキャンプでした。

応募用紙は、締め切りの日の午前1時過ぎからtwitterで"#moudamedaJP"などと呟きながら、朝までずっと書いてました。
応募用紙締め切りの前日まで東京にいたりと色々あり (来年応募しよう...) などと勝手に思っていたのですが、いざ考えてみると高校の時に一度応募して落ちてしまったことなどを思い出して、
やっぱり今年行きたい!とテンションが上がってきたのでウオオオオオと書いてました。
内容はいろいろ書いた気がします。一人では気付けないことも沢山あるので、沢山の知識を持った凄い方々が集まるセキュキャンで、脆弱性やバイナリについて学びたかったのでございました。
深夜の勢いで書いたので色々アレでしたが、応募して良かったです。

そして、受かった後はkadaiがでます。kadai。
私はkadaiの解答がほんとmoudamedaだったので、もっと頑張ろうと思いました...

さて、スケジュールはこんな感じでした!
1日目:開校式や共通講義。サイバー犯罪についてなどの特別講義がありました。オリエンテーションやグループワークなども。
2日目:ついにクラス別講義です。解析ツールの使い方などを学び、アセンブラ読経やマルウェア解析を行いました。
3日目:マルウェア解析についての発表。脆弱性あふれるプログラムの修正と、各々で修正されたプログラムを攻撃し合いました。夜はヒューリスティック検知エンジンについて学び、その改良を行いました。その後、BoFとチューターの方の発表がありました。
4日目:ヒューリスティック検知エンジンについての続き、発表。その後CTFです!
5日目:グループワークや各クラスの発表、CTFの模範解答の発表。閉校式。本の争奪戦。

簡単にまとめても重量感ありますね・・・。それだけ内容が濃かったです。
講義は本当にどれも楽しく、ためになりました。これを礎にこの先、頑張りたいです。
また、普段お会いすることの出来ないような方々からお話を伺うことが出来てとても幸せでした!うおお。
twitterで交流があった方とも実際にお会いできて楽しかったです!

問題のCTFではあまり役に立てませんでした・・・。いや、とても楽しかったですけどね!
課題の問題が解けなかった悔しさがあったので、ひたすらソフトウェアの分野の問題を解いていました。5問しか解けなかったので悔しいでござる・・・。

セキュリティキャンプの良いと思ったところは、自分のクラスの分野の知識の足りない所だけでなく、他のクラスの方々からも自分の知らない知識について沢山学ぶ事ができるところですね!
全てのクラスの教材が頂ける上に、CTFでは全ての分野の問題が出題されるので、他のクラスの方から問題の解説を受けるとoh...となりました。調べることが沢山増えましたね!

頂けた本の中で一番嬉しかったのは、"12ステップで作る 組込みOS自作入門"です!さっそく読みます。

要するに内容も濃いし楽しいし最高でした!モチベーションもめちゃくちゃ高まりました。知識の無さも痛感しました...
俺俺ライブラリもどんどん開発したいですね。あとはアウトプットを増やしたいです。

余談:
朝起きるのがめちゃくちゃ辛かったです。あとは これはPyhtonという言語で、アパ水とスリッパ。

うああ,読み返すと普通に恥ずかしいですね!
まあ,ではではいってみましょー

読み方

お手元にOllyDbgとダウンロードしてきたa.zipをご用意下さい.
ちなみに,Windows 7(x64)にて,OllyDbg 1.10を使っています.
では,

main関数まで

  1. a.zipを解凍して下さい.普通のzipファイルです d=(^o^)=b
  2. a.exeは実行しても何も表示してくれないので,a.exeをOllyDbgで開きます.
  3. メモリウィンドウを開いてみてみると,UPXでパックされていますね!なのでアンパックしましょう(今回は手動で).f:id:yutopp:20120906140343p:plain
  4. プログラムの実行(F9)か,ステップオーバー(F8)を数回かカチカチしてntdllを抜けると,a.exeの中身です.いきなりPUSHADが見つかるので,メモリにブレークポイントを仕掛けます。(左下のカラムのHex dumpと書いてある所で,Ctrl+gを押し,出てきたダイアログにespと入力しokを選択すると,スタックと同じアドレスの位置に移動してくれるので,任意の場所を右クリックし,BreakpointメニューのHardware, on accessのByteを選択します.このスクリーンショットでは灰色っぽくなっているところに仕掛けてあります.)f:id:yutopp:20120906140356p:plainf:id:yutopp:20120906140400p:plain
  5. おもむろにプログラムを実行させます(F9).するとPOPADとJMPがある良い感じのところでブレークポイントが引っかかりますね!うまいことアンパックされているはずです.(途中で止まってしまう場合も,スクリーンショットの場所にたどり着くまで何回か試してみて下さい!)f:id:yutopp:20120906140434p:plain
  6. 次回から楽できるようにJMP命令の位置にプレークポイントを仕掛けときましょう.JMP命令のある行を選択し,F2を押します(右クリック,BreakpointにあるToggleです).赤くなればうまくいってます.f:id:yutopp:20120906134332p:plain
  7. マニュアルアンパックっぽいサムシングも終わったので,JMP命令をステップオーバーで進めます.すると本来の中身が展開されているはずです.(あってるのか・・・?)f:id:yutopp:20120906140657p:plain
  8. 段々読みにくくなってきました.そこで,右クリック,AppearanceのHighlightingにあるJumps'n'callsを選択します.カラフルになってコードが追いやすくなると思います.
  9. 次は,main関数を探します.mainにはargc,argv,envp(環境変数)の3つの引数が渡されるので,コマンドラインに関連するっぽい部分とPUSH 3つを探してみます.その付近のcallがmainの呼び出しのはずなので,ステップイン(F7)します.f:id:yutopp:20120906140914p:plain
  10. では,mainの中身を読み進めましょう!f:id:yutopp:20120906140743p:plain

mainから最後まで

mainの中身のネタばらしをすると,GetLocalTimeで特定の日付の時だけ特別な動きをするようになってることと,各ルーチンで謎の演算をしていること,callに対してPOP EAXとJMP EAXで戻っていること,それっぽい文字列の"seccamp 2012!!!"付近のコードはダミーだということくらいです d=(^o^)=b
上のスクリーンショットの例だと,003D1C44から003D1C59の間の小細工と,GetLocalTimeの分岐に続くPOP EAX // ADD EAX, 2 // JMP EAX がキモです.
003D1C4F E8 0A000000 CALL a.003D1C5E の下にある,003D1C54 B8 4258FFE0 MOV EAX,E0FF5842 を見ればすぐ分かると思います.

  1. とりあえず,特定の日付の時だけに飛ぶルーチンにいつでも飛べるように,機械語を書き換えてしまいましょう.GetLocalTimeの下,MOVZXの行を選択し,アセンブル(スペースキー)します(書き換えるアドレスは個々で違うと思うので,適宜読み替えて下さい.赤い四角で囲んだところがキーです).f:id:yutopp:20120906143808p:plain
  2. JMP命令をステップオーバーします.
  3. すると,戻り先のアドレスが2Byteずれたことによって,MOV EAX,E0FF5842 が POP EAX // JMP EAX に変わります.もう終わりが近いですね,JMP命令をステップオーバーします.f:id:yutopp:20120906150045p:plain
  4. 残りは,VirtualAllocが確保しているアドレスを監視,展開された内容をダンプし,utf-8の文字列として読み込むだけです!f:id:yutopp:20120906150902p:plain

おわりに

という訳で簡単ながらも遊んでみました.これからは,複雑なプログラムの内容も読み解けるように努力していきたいです!
おまけに,このプログラムを作るのに使ったソースコードを載せておきますね!
VC10でコンパイル出来ます.

encode.cpp

#include <fstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <numeric>

int main()
{
	std::ifstream ifs( "src.txt", std::ios::binary );
	if ( !ifs ) {
		return -1;
	}
	std::istreambuf_iterator<char> begin = ifs, end;

	std::vector<char> bin;
	std::copy( begin, end, std::back_inserter( bin ) );

	std::for_each( bin.begin(), bin.end(), []( char& c ) { c = c ^ 0xcc; } );

	std::ofstream ofs( "encoded.csv", std::ios::binary );
	ofs << std::hex;
	std::for_each( bin.cbegin(), bin.cend(), [&ofs]( char const& c ) mutable {
		ofs << "0x" << static_cast<int>( c ) << ", ";
	} );
	ofs << "0x0";
}

a.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cstdint>

#include <Windows.h>

unsigned char const src[] = {
	#include "encoded.csv"
};

void a() { std::cout << "a!!" << std::endl; }
void b() { std::cout << "b!!" << std::endl; }
void c() { std::cout << "c!!" << std::endl; }
void d() { std::cout << "d!!" << std::endl; }
void e() { std::cout << "e!!" << std::endl; }
void f() { std::cout << "f!!" << std::endl; }
void g() { std::cout << "g!!" << std::endl; }
void h() { std::cout << "h!!" << std::endl; }
void i() { std::cout << "i!!" << std::endl; }
void j() { std::cout << "j!!" << std::endl; }

int key = 53, sign = 0;

int main()
{
	__asm {
		push ok;
		call f_hoge;
		_emit 0xB8;	// mov eax
		_emit 0x42;     // d=(^o^)=b
		pop eax;
		jmp eax;
	}

	goto l_last;

f_hoge:
	SYSTEMTIME st;
	::GetLocalTime( &st );

	if ( st.wYear == 2012 && st.wMonth == 8 && st.wDay == 18 ) {
		goto f_hoge_ok;
	}

//f_hoge_ng:
	__asm {
		mov eax, 0xdeadbeef;
		shr eax, 4;
		mov key, eax;
	}

	__asm {
		pop eax;
		jmp eax;
	}

f_hoge_ok:
	__asm {
		mov eax, 100;
		shr eax, 2;
		add eax, eax;
		lea eax, [eax + eax * 2];
		add key, eax;
		inc key;
	}

	__asm {
		pop eax;
		add eax, 2;
		jmp eax;
	}

	
//dummy:
	goto f_hoge;
	std::cout << "seccamp 2012!!!" << std::endl;

	int num = 0;
	std::cin >> num;
	if ( num == 1 )
		a();
	else if ( num == 1 )
		b();
	else if ( num == 2 )
		c();
	else if ( num == 3 )
		d();
	else if ( num == 4 )
		e();
	else if ( num == 5 )
		f();
	else if ( num == 6 )
		g();
	else if ( num == 7 )
		h();
	else if ( num == 8 )
		i();
	else if ( num == 9 )
		j();

	{
		std::vector<int> v;
		for( int i=0; i<0xdeadbeef; ++i ) {
			v.push_back( i );
		}

		std::copy( v.cbegin(), v.cend(), std::ostream_iterator<char>( std::cout, ", " ) );
	}

	{
		struct h
		{
			int fact(int n)
			{
				return n == 0 ? 1 : n * fact( n - 1);
			}
		};

		h i;
		i.fact( 500 );
	}

ok:
	char *const p = reinterpret_cast<char *>( ::VirtualAlloc( nullptr, sizeof( src ), MEM_COMMIT, PAGE_READWRITE ) );
	if ( !p ) {
		return -1;
	}

	::Sleep( 500 );

	for( std::size_t i=0; i<sizeof( src ); ++i ) {
		p[i] = src[i] ^ key;
	}

	std::fill( p, p + sizeof( src ), 0 );
	::VirtualFree( p, sizeof( src ), MEM_DECOMMIT );

	__asm mov eax, 0;

l_last:
	int i;
	__asm {
		mov i, eax
	}

	return i;
}

では!

セキュリティキャンプ2012に参加しました

参加しました!ソフトウェアセキュリティ組です。
とにかく楽しかったです!うおお。

なんと言いますか、感想を実行形式に突っ込んでみました!今回のキャンプで学んだ事を詰め込んだので、マルウェア解析っぽい気分で解析してみて下さい。あ、マルウェアじゃないですよ!
CTFの問題を参考にしているので、某問題を解けた方には簡単だと思います。
加えて、時間を割いても出てくるのは私の感想文だけです!!!

a.zip

それでは! d=(^o^)=b

少しですが、写真も載せておきますね!アパホテル最高でした。
f:id:yutopp:20120818154616j:plain
f:id:yutopp:20120815063456j:plain

DAizu #1 に参加してきた。

f:id:yutopp:20120430185737j:plain:w340
DAizu #1 - [PARTAKE]

会津大で行われたD言語勉強会に参加してきました!
実際D言語の他に、Dの付く言語であれば今日はOKとのことだったので、Dartも布教してきました。
未完成のスライドで挑んでしまったので、次回は完成させてリベンジしたい。

感想としては、実際にD言語についてのお話を生で聞けてとても勉強になりました。
初回ということで人数もそれほど多くなかったため個人個人が質問しやすかったこともあり、気になる点をバンバン聞くことが出来たのも良かったです。
発表者の方々、ご丁寧に答えて下さってありがとうございました。

具体的には、「簡単なD言語の紹介」の後に「ctpg - Compile Time Parser Generator」といった発展系の発表があり、D言語の文法や機能を実例とともに学ぶことができました。
また、C APID言語用にバインドしたDeimos(ダイモス)ライブラリの発表もあり、「こんなのもあるんだ!」と驚きでした。DartのAPIも移植して下さい。
D言語erに「これはC++でも・・・出来る?」といった質問をされるといったいじめを受けたことも報告しておきますね。

さて、D言語はコンパイル時に何でも出来る言語といった認識があったため、D言語の勉強会であるDAizuも開始と同時にスライドを渡されて終了するのではないかと心配していましたが、そんなことは無く安心しました。
そして、次回もDAizuやることになりました!そのうちPARTAKEにヒョッと立つと思います。

D言語・Dの付く言語の "D" という意味だけでなく、"Developer" といった意味も含めて色々な内容にしても良いね、みたいな話もしてきました。
皆さんもぜひぜひ次回は参加してみてはいかがでしょうか!

DartVM (rev5804) に渡せるオプション

rev5804時点のDartVMに渡せるオプションを纏めてみました。
違う点がありましたら、ぜひ教えて下さい><

オプション名 デフォルト値 コメント
deoptimization_counter_threshold int 5 "How many times we allow deoptimization before we disallow certain optimizations"
disassemble bool false "Disassemble dart code."
code_heap_size int Heap::kCodeHeapSizeInMB "code heap size in MB, e.g: --code_heap_size=8 allocates a 8MB old gen heap"
compiler_stats bool false "Compiler stat counters."
disable_privacy bool false "Disable library privacy."
disassemble_stubs bool false "Disassemble generated stubs."
enable_asserts bool false "Enable assert statements."
enable_checked_mode bool false "Enabled checked mode." (注釈: このオプションは、--enable_assertsと--enable_type_checksを同時に設定するのと同じ意味。)
enable_type_checks bool false "Enable type checks."
gc_at_alloc bool false "GC at every allocation."
generate_gdb_symbols bool false "Generate symbols of generated dart functions for debugging with GDB"
ignore_unrecognized_flags bool false "Ignore unrecognized flags."
inline_alloc bool true "Inline allocation of objects."
inline_cache bool true "enable inline caches"
intrinsify bool true "Instrinsify when possible"
new_gen_heap_size int 32 "new gen heap size in MB, e.g: --new_gen_heap_size=64 allocates a 64MB new gen heap"
old_gen_heap_size int Heap::kHeapSizeInMB "old gen heap size in MB, e.g: --old_gen_heap_size=1024 allocates a 1024MB old gen heap"
optimization_counter_threshold int 2000 "function's usage-counter value before it is optimized, -1 means never."
print_ast bool false "Print abstract syntax tree."
print_bootstrap bool false "Print the bootstrap source."
print_classes bool false "Prints details about loaded classes."
print_flags bool false "Print flags as they are being parsed."
print_flow_graph bool false "Print the IR flow graph."
print_ic_in_optimized
(TARGET_ARCH_IA32が定義されているときのみ)
bool false "Debugging helper to identify potential performance pitfalls."
print_scopes bool false "Print scopes of local variables."
print_stack_trace_at_throw bool false "Prints a stack trace everytime a throw occurs."
print_stop_message bool true "Print stop message."
print_tokens bool false "Print scanned tokens."
report_usage_count bool false "Track function usage and report."
silent_warnings bool false "Silence warnings."
time_all bool false "Time all functionality"
trace_bailout bool false "Print bailout from new compiler."
trace_class_finalization bool false "Trace class finalization."
trace_compiler bool false "Trace compiler operations."
trace_deopt bool false "Trace deoptimization"
trace_functions bool false "Trace entry of each function."
trace_ic bool false "trace IC handling"
trace_intrinsified_natives bool false "Report if any of the intrinsified natives are called"
trace_isolates bool false "Trace isolate creation and shut down."
trace_natives bool false "Trace invocation of natives"
trace_optimization
(TARGET_ARCH_IA32が定義されているときのみ)
bool false "Trace optimizations."
trace_parser bool false "Trace parser operations."
trace_patching bool false "Trace patching of code."
trace_resolving bool false "Trace resolving."
trace_runtime_calls bool false "Trace runtime calls."
trace_type_checks bool false "Trace runtime type checks."
trace_type_finalization bool false "Trace type finalization."
use_new_compiler bool TARGET_ARCH_X64が定義されているときtrue。そうでないときにfalse "Try to use the new compiler backend."
use_slow_path bool false "Set to true for debugging & verifying the slow paths."
verbose_gc bool false "Enables verbose GC."
verify_after_gc bool false "Enables heap verification after GC."
verify_before_gc bool false "Enables heap verification before GC."
verify_implements bool false "Verify that all classes implement their interface."
verify_on_transition bool false "Verify on dart <==> VM."
warning_as_error bool false "Treat warnings as errors."
worker_timeout_millis int 5000 "Free workers when they have been idle for this amount of time."


おまけ:テスト用オプション(テスト順)

オプション名 デフォルト値 コメント
basic_flag bool true "Testing of a basic boolean flag."
parse_flag_bool_test bool true "Flags::Parse (bool) testing"
string_opt_test charp NULL "Testing: string option."
entrypoint_test charp "main" "Testing: entrypoint"
counter int 100 "Testing: int flag"