yutopp's blog

サンドバッグになりたい

LLVMと俺俺ランタイムで例外を実装する(その1)

環境: Arch Linux(x86_64), LLVM 3.4, GCC 4.9.0

文鳥言語の言語機能に例外を追加したかったので,先にLLVM側の調査とランタイムを実装しました(進捗).自分で思い出すために後々読み返しそうなので,例外ハンドリングについてメモっておきます.

何かの参考になれば幸い.間違いなどは指摘していただけると嬉しいです.

今回実装したのはLinuxx86_64用の実装でtable-basedのものです.

コードはこちら yutopp/llvm-exception-handling-test

例外ハンドリング

LLVMの例外ハンドリングのドキュメントはこちら Exception Handling in LLVM

今回は,このドキュメントで示されている"Itanium ABI Zero-cost Exception Handling"を元に自前の例外ランタイムを実装したことになりますが,このドキュメントは,CやC++で使われている例外ハンドリングについて深く説明しているため,実際に言語のランタイムに実装するとなると少し物足りない感じがありました.でも読みやすくてスバラシイ〜

そして,次に参考にしたのが,LLVM PROJECT BLOG.New libunwind implementation in libc++abi

大体

例外のunwindには,libcxxabiに含まれるcxa*例外関数群が要求するUnwind*関数群(高レベルAPI)と,old HP libunwind projectで定義されたインターフェースであるunw*関数群(低レベル操作)の二通りがある.

多くのアーキテクチャでは”ゼロコスト”例外をC++に使っている.ゼロコストとは,例外が発生しない通常の実行では余計な命令が生じないものである.しかし,例外が投げられた場合には,ランタイムはどのようにレジスタをリストアし,現在のスタックフレームからcatch項まで"unwind"するかを,side tableを参照し把握しなければならない. スタックフレームを修正,全てのレジスタをリストアし,適切にスレッドをcatch節にresumeさせることが,libunwindの主な用途である.

みたいな事が書いてありました.

Itanium C++ ABI: Exception Handling でいうと,”libcxxabiに含まれるcxa*例外関数群” が”Level II: C++ ABI”以降,”Unwind*関数群”が,”Level I. Base ABI”になるようです.

従って,今回はLLVMと共に自前の例外ランタイムを実装したいので,このC++ ABIを使わずに,この部分を自前で実装すればいいことになります.また,Level 1 ABIの実装は共通なので,既にある実装を使うことができます. というわけで,Level 1 ABIについては,今回は既存の実装を利用しています(申し訳 of the world).

フォーマット

LLVMが生成してくれるASM テーブルフォーマット(ドキュメントてきとう訳)

例外が投げられた際に,どんな処理を取るべきか決定するために例外ハンドリングランタイムに使われるテーブルが2つあります.

Exception Handling Frame

例外ハンドリングフレームであるeh_frameは,DWARF debug infoに使われているunwind frameにとても良く似ています. このフレームは,現在のフレームをtear downし,以前のフレームの情報をリストアするために必要な全ての情報を含んでいます. コンパイル単位における,それぞれの関数の例外ハンドリングフレームに加え,全ての関数の共通する情報を定義した一般的な例外ハンドリングフレームも存在します.

Exception Tables

例外テーブルは関数のコードのある部分で例外が投げられた際に,どのアクションを起こすべきか,という情報を含んでいます. 例外テーブルを必要としないリーフ関数(注:関数テーブルエントリ(スタックフレームなど)を使用しない関数のこと)やnon-throwな関数のみを呼び出す関数を除いて,各関数には一つの例外テーブルが存在します.

これらのフォーマットの読み込みをコードに落とすのに,以下のスライドがとても参考になりました.

Compiler Internals: Exceptions and RTTI

また,例外処理で出てくる用語は以下の感じ

単語 意味
LSDA Language Specific Data Areaのこと.
landingpad 例外が投げられたあと,catch,またはclean upするための,ユーザーコードのセクションのこと.personality routineによってexception runtimeからコントロールを得た後,通常のユーザーコードに合流させるか,resumeによってランタイムに戻る,新しい例外をraiseするかといった目的に用いる.
personality routine C++(や他の言語)のランタイムライブラリにある,system unwind libraryとlanguage-specific exception handling semanticsとの間のインターフェースを提供する関数のこと.

LLVMでの流れ

  • landingpad 命令で例外の着地点をつくる
  • @llvm.eh.typeid.for を用いて例外を選択する

おわり

今回実装したもの

  • 言語固有の例外ハンドリングの関数(allocate, throw, resume, free)
  • personality routine

言語固有の例外ハンドリングの関数

C++ ABIを真似て適当に作った.

personality routine

今回の山場でした.unwindを行うライブラリと言語固有の機能のインターフェースを取り持つ関数です.

2段階のフェーズに分かれて呼ばれるようで,最初の探索フェーズで

  • LSDAの読み込み
  • landingpad の選択
  • call siteやaction_tableの読み込み
  • 適切なcatch節やclean upの選択
  • その情報の保存

を行い.

次の段階で,

  • 第一段階の情報の引き出し
  • 目的の節へのジャンプの登録

を行います.

C++D言語のランタイムの実装を参考にしました!

eh_personality.cc Source File

druntime/src/ldc/eh.d at ldc · ldc-developers/druntime

おわりに

くぅ〜疲れました!w

Binary Hacks ください.

その2に続く→

参考資料

dzeta.jp技術資料 - NPTLとC++例外処理 force_unwindの存在をこれで知りました.

g++の例外を捕まえよう!!(素手で)

exception handling | 0xdeadp0rk

Mono:Runtime:Documentation:LLVM

unwind自体の実装

gcc/libgcc/unwind-dw2.c at master · mirrors/gcc https://llvm.org/svn/llvm-project/libcxxabi/trunk/src/Unwind/UnwindLevel1.c

LLVM IRの構造の可視化をするメモ

LLVM IRの構造をグラフで見たかったので試してみました.メモ.

参考資料:

LLVM’s Analysis and Transform Passes

Visualizing code structure in LLVM

環境: Arch LinuxLLVM 3.4,graphviz 2.36.0

試す

試しに使ったC++コード(test.cpp)

ProcGarden - test.cpp (libc++がおかしいのでclangでなくGCCでビルドしています…ウッ)

そして,この test.cppclang++ test.cpp -emit-llvm -c -SLLVM IRにした結果は以下(test.ll)

ProcGarden - test.ll

このLLVM IRとoptコマンドを用いてdotファイルを生成し,それをgraphvizで可視化する.

CallGraph

opt test.ll -dot-callgraph > /dev/null

e.g. CallGraphをgraphvizを用いてPNGにする

dot -Tpng callgraph.dot > callgraph.f.png

f:id:yutopp:20140503003625p:plain

CFG

opt test.ll -dot-cfg > /dev/null

e.g. 関数fのCFGをgraphvizを用いてPNGにする

dot -Tpng cfg._Z1fv.dot > cfg.f.png

f:id:yutopp:20140503003546p:plain

Dominance Tree

opt test.ll -dot-dom > /dev/null

e.g. 関数fのDominance Treeをgraphvizを用いてPNGにする

dot -Tpng dom._Z1fv.dot > dom.f.png

f:id:yutopp:20140503003640p:plain

Post-dominance Tree

opt test.ll -dot-postdom > /dev/null

e.g. 関数fのPost-dominance Treeをgraphvizを用いてPNGにする

dot -Tpng postdom._Z1fv.dot > postdom.f.png

f:id:yutopp:20140503003658p:plain

おわり

次はLLVMで例外を使ってみる.

鳥小屋でOpenJDK9を動かしたときのメモ

オンラインコンパイラにOpenJDK9を入れた後にハマったのでメモ

オンラインコンパイラの実行環境ではメモリリソースに制限をかけている(rlimit_asで1.5GB程度)ので、そのままのJVMの起動ではリソース不足で動かなかった。だいたいJVMが2GB使うようだったので微妙に足りない…。

結局解決できたので、そのオプションを書いておく。
Java8からPermGenというものがMetaspaceというものに変わったようなのでそこもチェックする。

まずヒープ
-Xms 64m
-Xmx 128m

スタック
-Xss 512k

Metaspace
-XX:MaxMetaspaceSize=128M
-XX:MetaspaceSize=64M

ここまで指定すると
"Could not allocate metaspace: 1073741824 bytes"
と遺してJVMが死んでしまう。

そこで、以下のようにオプションを指定したところエラーは発生しなくなった。
-XX:CompressedClassSpaceSize=32M

-XX:CompressedClassSpaceSizeのデフォルト値は1024Mであり、エラーの内容とも一致しているのでこれが原因のはず。
エラーの発生箇所がjdk8/awt/hotspot: 209aa13ab8c0 src/share/vm/memory/metaspace.cppだったので、この値を変えてみたのだけど、結局これはなんなのだろう…

とりあえず、これでJVMのメモリ使用量が1GB程度になって無事動かせるようになった。


参考

文鳥言語とBoost.Spirit.Qi Tips - C++ Advent Calendar 2013(11日目)

これは C++ Advent Calendar 2013 - PARTAKE 11日目の記事です。

この記事では俺々プログラミング言語の紹介と、C++処理系を作るにあたって便利そうなBoost.Spirit.QiのTipsを紹介します。
Boostは1.55.0が対象です。

文鳥言語とは

文鳥言語とは、私が趣味で作っているプログラミング言語です。
yutopp/rill · GitHub

C++は(人間の)プログラマが書いていて楽しく感じるように作られている言語ですが、文鳥言語は文鳥が書いていて楽しく感じられるように作られています。
文鳥 - Google 検索
カワイイヤッター!(?)

文鳥言語を支える技術

文鳥言語の実装には、全体的にC++11、構文解析器にBoost.Spirit.Qi、コード生成にはLLVMを用いています。
構文解析器とコード生成にライブラリを使っている時点で、言語を自分で作っている感は薄いのですが、常にそれなりに動く状態で遊べるのでとても楽しいのです。

今の段階では、このようなコードをコンパイルすることができます。単純なFizzbuzzです。

def main(): int
{
    print( "hello, bunchou lang on Linux!!!bunbun!\n" );
 
    val i = 1: int mutable;
    while( i < 100 ) {
        if ( i % 15 == 0 ) {
            print( "Fizzbuzz " );
        } else if ( i % 5 == 0 ) {
            print( "Buzz " );
        } else if ( i % 3 == 0 ) {
            print( "Fizz " );
        } else {
            extern_print_int( i ); print( " " );
        }
 
        i = i + 1;
    }
    print( "\n" );
    // Test
    overload( 2, 5 );
    overload( "bun!" );
 
    return 0;
}
 
def overload( val a: int, val b: int ): void
{
    print( "====================\n" );
    print( "test_scope\n" );
    print( "====================\n" );
 
    val i = 42: int mutable;
    {
        val i = 72: int;
        print( "inner: " ); print_int( i );
    }
    print( "outer: " ); print_int( i );
}
 
 
def overload( ref s: string ): void
{
    print( "====================\n" );
    print( s );
    print( "\n" );
}
 
//
extern def extern_print_int( val :int ): void "put_string2"; 
 
def print_int( val i: int ): int { extern_print_int( i ); print( "\n" ); }

出力バイナリの実行結果

hello, bunchou lang on Linux!!!bunbun!
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 Fizzbuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 Fizzbuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 Fizzbuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 Fizzbuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 Fizzbuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 Fizzbuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz 
====================
test_scope
====================
inner: 72
outer: 42
====================
bun!

かわいいですね。今は基礎部分に力を入れて開発をしています。いつか、これでリンカなど作りたいですね。

さて、この言語処理系を作るにあたって、Boost.Spirit.Qiが大活躍しています。

Boost.Spirit.Qi Tips

Boost.Spirit.Qi については、インターネッツを検索するとためになる資料が出てきますのでそちらを参考にして下さい。

さて、Qiについて色々調べていると、様々なつぶやきが散見されます。

  • とっつきにくい
  • コンパイル時間がBoostする
  • コンパイルエラーが意味不明
  • 非常に明快で分かりやすい

このコンパイルエラーが意味不明、というのがとっつきにくい最大の問題だと思います。

私が初めてBoost.Spiritに触れたのは中学3年生の頃(某とは関係ありません)でした。Boostは1.43.0でVC++2005な環境だった気がします。
その時はSpiritのコンパイルエラーに精神を破壊されたのですが、今ならSpirit.Qiをとても楽に使いこなせるはずです。

そう、Clangとならね。

Clangを使う

パーサを書くときは、Clangを使ってコンパイルするのがオススメです。
Clangはコンパイルエラーが優しいという事で有名ですが、この優しさがQiを使うときにも活きてくるためです。

例えば、以下のようなコードがあるとします。

#include <iostream>
#include <vector>
 
#ifndef BOOST_SPIRIT_USE_PHOENIX_V3
# define BOOST_SPIRIT_USE_PHOENIX_V3
#endif
#include <boost/spirit/include/qi.hpp>
 
#include <boost/fusion/include/adapt_struct.hpp>
 
struct wrapper
{
    std::vector<int> v;
};
 
BOOST_FUSION_ADAPT_STRUCT(
    wrapper,
    (std::vector<int>, v)
)
 
int main()
{
    namespace qi = boost::spirit::qi;
 
    std::string const test_input = "1, 2, 3, 4, 5";
 
    auto it = test_input.cbegin();
    auto const last = test_input.cend();
 
    wrapper result;
 
    auto const r = qi::int_ % qi::lit( ',' );
 
    auto const s = qi::phrase_parse( it, last, r, qi::ascii::space, result );
    assert( s );
    assert( it == last );
 
    for( auto const& i : result.v )
        std::cout << i << " ";
    std::cout << std::endl;
}

これはコンパイルエラーになるコードなのですが、ここで、Clang と GCC からのコンパイルエラーをご覧ください。(Wandboxありがとうございます)

GCCのコンパイルエラーはパッと見どの箇所がエラーの原因なのか分かりにくく、つらい感じがします(19行目)。
今回はシンプルなコードなので比較的特定しやすいのですが、構文のruleが増えてくると、この分かりにくさは地獄を生み出します。

比べてClangのコンパイルエラーの優しさといったらなんでしょう!11行目でバッチリ`value_type`が無いと教えてくれていますね。
これで、as でくくって要件を満たす一時オブジェクトを渡してやればいいんだな、とすぐに理解することが出来ます。

auto const r = qi::int_ % qi::lit( ',' );

auto const r = qi::as<std::vector<int>>()[ qi::int_ % qi::lit( ',' ) ];

に修正。やりました!

TemplateAliasesを使う

ruleをgrammerにまとめる場合はメンバにrule型の宣言を置くことになり、型を推論させることが出来ません。

なので、例えば

qi::rule<Iterator, ast::statement_ptr(), skip_grammer_type> statement_;

のような宣言を大量に書くことになるはずですが、Iterator や skip_grammer_type などを毎回書くのが面倒なので

template<typename T>
using rule = qi::rule<Iterator, T, skip_grammer_type>;

などとしておくと

rule<ast::statement_ptr()> statement_;

と書けるようになるので幸せだと思います。

これはVC++2013で使えるので使わない手はありませんね!
C++11/14 Core Language Features in VS 2013 and the Nov 2013 CTP - Visual C++ Team Blog - Site Home - MSDN Blogs

ruleを細かく分ける

ruleを細かく分割することによって、コンパイルエラーとなる箇所の特定がとても楽になります。
上記の2つと合わせて、rule を細かく分けるのがオススメです。

rule の 型をしっかり見る

rule<ast::statement_ptr()> statement_;

ruleに渡すast::statement_ptr()などの()は忘れがちでハマるので気をつけましょう。
引数を渡すruleを作ることが少ないので忘れがちになりますね…

Phoenix V3 を使う

Spirit関連のファイルをインクルードする前に

#define BOOST_SPIRIT_USE_PHOENIX_V3 1

とすることで、Boost.Phoenix 3が使われるようになります。
関数オブジェクトを作るのが楽になっているはずなので、Phoenix は 3 を使いたいところ。

make_shared を作る

文鳥言語では、ASTの組み変えが発生しそうなのでコピーコストが低いであろうshared_ptrを使ってASTを構築しています。
なので、SemanticActionにてオブジェクトを生成する必要があるのですが、Phoenixには相当の関数がデフォルトで無いようなので作ります。

template<typename T>
struct make_node_pointer_lazy
{
    typedef std::shared_ptr<T> result_type;

    template<typename... Args>
    auto operator()( Args&&... args ) const
        -> result_type
    {
        return std::make_shared<T>( std::forward<Args>( args )... );
    }
};

template<typename T, typename... Args>
auto make_node_ptr( Args&&... args )
    -> decltype( boost::phoenix::function<make_node_pointer_lazy<T>>()( std::forward<Args>( args )... ) )
{
    return boost::phoenix::function<make_node_pointer_lazy<T>>()( std::forward<Args>( args )... );
}

(Allocatorを考慮するの忘れていた…)
ひとまずコレで

some_rule_[qi::_val = make_node_ptr<HogeClass>( qi::_1, ... )]

のようにnodeが簡単に作れるようになるので、便利かもしれません。

参考: Boost.Phoenix V3 - 関数のbind化 - Faith and Brave - C++で遊ぼう

パース時に位置情報を取る

c++ - boost::spirit access position iterator from semantic actions - Stack Overflow
参考になるのでどうぞ…
(line_pos_iteratorの実装ってどうなんでしょう…ウーン)

Assertion `rhs.f && "Did you mean rhs.alias() instead of rhs?"' failed. is 何

未初期化のruleを直に代入すると、このassertionにひっかかります。

#include <iostream>
#include <vector>

#ifndef BOOST_SPIRIT_USE_PHOENIX_V3
# define BOOST_SPIRIT_USE_PHOENIX_V3
#endif
#include <boost/spirit/include/qi.hpp>

#include <boost/fusion/include/adapt_struct.hpp>

template<typename Iterator>
class code_grammer
    : public boost::spirit::qi::grammar<Iterator, int>
{
public:
    code_grammer()
        : code_grammer::base_type( a_ )
    {
        a_ = b_;

        b_ = boost::spirit::qi::int_;
    }

private:
    boost::spirit::qi::rule<Iterator, int> a_, b_;
};

int main()
{
    namespace qi = boost::spirit::qi;

    std::string const test_input = "42";

    auto it = test_input.cbegin();
    auto const last = test_input.cend();

    int result;
    code_grammer<decltype(it)> r;

    auto const s = qi::phrase_parse( it, last, r, qi::ascii::space, result );
    assert( s );
    assert( it == last );

    std::cout << result << std::endl;
}

code_grammerの

a_ = b_;

が、未初期化の b_ を代入しているのでダメですね。

解決策

  • 素直に a_ と b_ の代入位置を入れ替える
  • .alias() を使う
a_ = b_.alias();
  • %= を使う
a_ %= b_;

おわりに

ここまでBoost.Spirit.Qiを使って構文解析器を作った段階で踏み抜いた罠を紹介しました。
Spiritは実際便利なのであらゆる場所で使われているはずなのですが、少し初見殺しなところがある上に、罠から抜け出す術が中々載っていないので、Tipsが少しでも役に立てば幸いです。

では

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連鎖: 台湾に行きました。