ゼロ番地を先頭とするページにマップする

mmapのflags引数にMAP_FIXEDフラグを指定することで、OSの実装によってはゼロ番地を先頭とするページにマップできます*1

たとえば、i386以降のCPU, Vine Linux 4.0, gcc-4.1.1を使った環境で以下のコードをコンパイルして実行するとゼロ番地にアクセスできます。

#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>

int main(){
int* p = (int*)mmap(0, getpagesize(), PROT_READ | PROT_WRITE,
MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED, 0, 0);
*p = 1;

printf("*(int*)%d = %d\n", (int)p, *(int*)0);
return 0;
}

実行すると以下のようになります。

$ gcc main.c
$ ./a.out
*(int*)0 = 1
$

以下、注意点。

Cの仕様上では、start引数に0を指定しても数値の0を指すとは限りません。なぜなら、start引数の型はvoid*であり、Cの仕様ではポインタを書くべきところに書かれた0は、コンパイル時にヌル・ポインタに変換されることが保証されているからです*2(コンパイラがポインタ型の式だと判断できる場合のみ)。

なお、C++でもほとんど同様のようです*3。自分には、CとC++の違いは、C言語の場合、#define NULL (void*)0 か #define NULL 0 どちらでもありうるが、C++だと #define NULL (void*)0 がありえないということしかわかりませんでした。

よって、ハードウェア, OS, C/C++のコンパイラによっては、start引数で渡す値がコンパイル時に0ではない値に変換されているかもしれないので、ソースコードでstart引数に0を指定したからといって、実行時にmmapでマップされたページが必ずしもゼロ番地ではないかも知れないことに注意です。

以上、何の役に立つかわからないけど面白かったのでメモっときます。

ちなみにWindowsの場合、ゼロ番地から64KB分*4のアドレスをユーザプログラムのプログラマがVirtualAlloc APIで確保(予約)することはできません。これは、ヌル・ポインタが指すアドレス先に値を代入しようとしたときに、必ずメモリアクセス違反が発生するようにするために、意図的にそう決まっています*5

ということは、Windowsが動くような環境において、ヌル・ポインタが0と一致する(させる)のは当然だとMicrosoftは考えているのでしょうね。

*1:SUSv3では、「MAP_FIXEDフラグを指定した場合、start引数はマップされるページのヒントとなるアドレスではなく、マップさせたいページのアドレスを意味するようになり、マップに失敗した場合はエラーを返す」としか書いてありません。よって、startに0を指定した場合は必ず失敗するようにmmapを実装しても仕様を満たします。

*2http://www.kouno.jp/home/c_faq/c5.html 5.2項

*3:注解 C++ リファレンスマニュアル 4.6: ISBN 4901280392 といっても、これ古い仕様みたいですけど・・・

*4:Windows2000の場合。Windows98だと4KB分

*5:Advanced Windows 13.2 :ISBN 4-7561-3805-5

最適化のトリビア

以下のコードがあったとします。

#include <stdio.h>

int main(int argc, char* argv[]){
int i;
if(argc > 1){
i = 10;
}

printf("i = %d\n", i);
return 0;
}

これをgcc 4.1.1でコンパイルして実行すると以下のようになります。

$gcc -O2 main.c
$./a.out
10        <-------注目
$./a.out 1
10
$./a.out 1 2
10

このような結果になるのには、ちゃんとした理由があります(コンパイラの視点にたった場合)。

iに対する代入がない段階において、iの値が何であるかは、Cレベルでは未定義です。これは、代入がない間のiの値をコンパイラが勝手に設定しても問題ないということを意味します。よって、コンパイル時に上のコードを以下のように読み替えても問題ないです。

int main(int argc, char* argv[]){
int i = 10;
if(argc > 1){
i = 10;
}

printf("i = %d\n", i);
return 0;
}

このコードを最適化すると以下のコードになります。

int main(int argc, char* argv[]){
printf("i = %d\n", 10);
return 0;
}

よって、a.outのコマンドライン引数に何も与えなくても(argc == 1でも)10が出力されます。

1へぇ。

static変数に対応するアドレスを探す(ELF format編)

共有ライブラリ上に存在する、あるstatic変数aのプロセス上でのアドレスを知りたいときがあります。apt-getでインストールした共有ライブラリをデバッグしたい時なんかがそうです。

最近、こういったアドレスを探すことが多いので、忘れないようにメモっておきます。

以下の話は、共有ライブラリが位置独立コード(PIC)としてコンパイルされていることを前提にしています。

あと、私はgccとx86系cpuを使って確認しているので、他の環境だと違う場合があります。

基本

共有ライブラリを使っているプロセスのメモリ利用状況をpmapコマンドやprocファイルシステムを使って確認することで、共有ライブラリのロード先がわかります。

共有ライブラリ名がhoge.soだとすると、

$ pmap 10000
08048000    4K r-x-- a.out
...<>...
b7f8e000    8K rwx-- foo.so
b7f94000    4K r-x-- hoge.so
b7f95000    4K rwx-- hoge.so
...<>...

上のpmapの結果から

hoge.soのロード先先頭アドレスは、b7f94000だとわかります。また、シンボルテーブルにstatic変数aの情報があるなら、簡単にaの共有ライブラリ内での相対アドレスがわかります。

あとは、以下の計算式、

(プロセス上での変数aのアドレス) = (共有ライブラリのロード先頭アドレス) + (変数aの相対アドレス)

で変数aのアドレスがわかります。

まあ、こんなのいちいち計算しなくても、gdbがやってくれます。gdbでプロセスにアタッチして、

p &a

とかすれば、変数aのアドレスがわかります。

シンボルテーブルがない場合

apt-getでインストールした共有ライブラリの場合、ファイルサイズを減らすために、シンボルテーブルがstripコマンドで削除されていることがあります。

この場合、簡単には変数aの相対アドレスを知ることができません。プログラムを実行させずに相対アドレスを調べるには、アセンブリコードを読んで相対アドレスを探すしかないです*1(たぶん)。

アセンブリコードだけでもよくわからないので、コンパイル元のソースコードも使います。

まず、ソースコードの中で変数aを操作する処理が入っているグローバル関数をまず探します。グローバル関数の中で変数aを操作していないのなら、グローバル関数からたどりやすい関数の内、変数aを操作する関数を探します。グローバル関数の相対アドレスは、ダイナミックシンボルテーブルに存在するので、objdumpで逆アセンブルした時、objdumpが適切にグローバル関数の先頭を表示してくれます。

最適化が影響しないかぎり、グローバル関数を基点として、ソースコードとアセンブリコードを比較していけば、変数aのGOTからの相対アドレスを判別できるアセンブリ命令が見つかると思います。

例えば、以下のソースコード、

a = 0;

に対応するアセンブリコード

movl $0x0 0x20(%ebx)

を見つけたとします。

0x20が、変数aのGOTからの相対アドレスです。

このとき、%ebxは、

%ebx = (ファイル内のGOT相対アドレス) + (共有ライブラリロード先頭アドレス)

です。

ファイル内のGOT相対アドレスは、objdump -Tコマンドで表示されるダイナミックシンボルテーブルのうち、

_GLOBAL_OFFSET_TABLE_シンボルのアドレスに対応します(gccの場合)

また、(_GLOBAL_OFFSET_TABLE_のアドレス) == (.got.pltセクションのアドレス)のようです。

共有ライブラリロード先頭アドレスは、最初の方法と同様にpmapコマンドを使って見つけられます。

以上の情報を使って、以下の計算式、

 (プロセス上での変数aのアドレス) = (変数aのGOTからの相対アドレス) + (_GLOBAL_OFFSET_TABLE_のアドレス) + (共有ライブラリロード先頭アドレス)

で変数aのアドレスがわかります。

うーん、何か説明がわかりにくいなあ。実際にアドレスを探している動画とか作ったほうがわかりやすいかも。

参考文献

GOTとかPICとかについては、以下の書籍が参考になります。

*1:ちなみに、staticではない大域変数なら、objdump -Tとか、nm -D とかして、ダイナミックシンボルテーブルから、相対アドレスを調べれば十分です。

仕様書等のリンク集

ソフトウェア実装の際、様々な仕様書を参考にすることがありますが、どんな仕様書がどこにあるのか忘れることがあるのでメモっておきます。

仕様書だけではなく、複数の仕様書について言及、比較をしている資料も挙げておきます。

オブジェクトファイルに関する仕様書等

  • Microsoft Portable Executable and Common Object File Format Specification: Windows上の実行可能ファイルとオブジェクトファイルに関する仕様書*1

http://www.microsoft.com/japan/whdc/system/platform/firmware/PECOFF.mspx

  • Tool Interface Standard (TIS) Portable Formats Specification: Linux/BSD系 OSの標準的なオブジェクトファイルであるELFに関する仕様書.そのほかにDwarf*2やOMFの仕様も書かれている

http://www.acm.uiuc.edu/sigops/rsrc/pfmt11.pdf

  • Introduction to Mach-O Programming Topics: Mac OS Xで使われるオブジェクトファイル形式Mach-Oを使ってプログラムを書く上で参考になるTopic集(Mach-Oの構造に関する記述含む)

http://developer.apple.com/documentation/DeveloperTools/Conceptual/MachOTopics/introduction.html

OSが提供する機能やその機能を利用するアセンブラ、C言語、C標準関数に関する仕様書等

  • Manpage of STANDARDS: C と UNIX の標準規格を昔から現在の物まで列挙してあります。各規格の関係を把握するのに役立ちます。

http://www.linux.or.jp/JM/html/LDP_man-pages/man7/standards.7.html

  • Calling conventions for different C++ compilers and operating systems: コンパイラ、OSの違いに伴うC++の呼び出し規約の違いに関する記述が主ですが、OSによるcallee-save registerやcaller-save registerの違い等についても書かれているのでC++とは関係なく参考になります

http://www.agner.org/optimize/

  • The Single UNIX Specification Version 3: 現在、多くのOSが準拠していると思われるUNIX OSとCに関する仕様書

http://www.unix.org/single_unix_specification/

プログラミング言語に関する仕様書等

  • RubySpec: Rubyの仕様は文書化されていないのですが、それだと困るっていうんで有志の人がRubyマニュアルやCRubyの実装を元に仕様ぽい規定を収集したもの。直接CRubyの実装を読むよりは、ずっと楽です。

http://www.headius.com/rubyspec/index.php/Main_Page

  • Python Reference Manual: Pythonの文法や機能に関する仕様書

http://docs.python.org/ref/ref.html

*1:仕様書をpdfではなくdocファイルで提供するあたりがMicrosoft的だなあ・・・

*2:ELFとともによく使われるデバッグ情報の一種

補足

バックトレースがうまくとれない件ですが、これに対処しようとした場合、test.rbのdebuggerメソッドでbreakした瞬間に、Ruby言語上のstack frameに関するデータ構造をアセンブラ(C言語)レベルで読み込んで解析する必要があると思います。

でも、これを言語実装者側のサポートなしに実現するのはかなり大変でしょう。大変な理由を思いつく限りで列挙すると、

  • Rubyのstack frameを拡張ライブラリが直接読み込むことができない?
    • Rubyの実装に詳しいわけではないので、直接読み込めないというのは勘なのですが、セキュリティの観点から考えて、拡張ライブラリがstack frameをいじれないのは当然だと思う
  • debuggerとdebuggeeが同一プロセスであるため、Rubyのstack frameに直接アクセスできたとしても、stackのどの部分がdebuggerのもので、どの部分がdebuggeeのものか区別が難しい
    • 同一プロセス上にあるから、gdbで言うところのprintコマンドが簡単に実現できるという利点もあるのですが、バックトレースは実装しにくくなります
    • debuggerとdebuggeeが同一プロセスであるというのは、C, Javaのデバッガと大きく異なる点でもあります

こんな感じでしょうか。

まあ、PythonやRubyの場合は、printやpを使ってデバッグしろってことでしょうかねえ。

デバッガの実装(Ruby/Python編)

最後に、Ruby,Pythonのデバッガの実装について調べてみました。

Pythonには、pdb。 Rubyにはdebug.rbというデバッガが存在します。

これらは、各言語が提供するフック関数を利用して実装されています。フック関数を設定する関数(メソッド)は以下になります。

  • Python
    • sys.settrace (Cレベルでは、ceval.cのPy_tracefunc関数*1 )
  • Ruby
    • Kernel#set_trace_func (Cレベルでは、eval.cのset_trace_func関数)

Pythonのsys.settraceの引数で渡した関数は、以下のタイミングで呼び出されます*2

  • call: なんらかの関数呼び出し時
  • line: Pythonインタプリタが新しい行を実行する時
  • return: 関数の呼び出しからreturnする寸前
  • exception: 例外が発生した時
  • c_call: (拡張ライブラリ等の)C関数が呼び出されるとき
  • c_return: C関数から返ってきたとき
  • c_exception: C関数内部でPythonの例外が発生した時

また、RubyのKernel#set_trace_funcの引数で渡した関数は、以下のタイミングで呼び出されます*3

  • “line” … 式の評価。
  • “call” … メソッドの呼び出し。
  • “return” … メソッド呼び出しからのリターン。
  • “c-call” … Cで記述されたメソッドの呼び出し。
  • “c-return” … Cで記述されたメソッド呼び出しからのリターン。
  • “class” … クラス定義、特異クラス定義、モジュール定義への突入。
  • “end” … クラス定義、特異クラス定義、モジュール定義の終了。
  • “raise” … 例外の発生。

フック関数が呼び出されるときに、そのときの文脈(どのようなローカル変数が存在するか、次に行われる処理では、どのクラスの何のメソッドを呼ぼうとしているのか等)が引数として渡されます。フック関数はそれを記録、処理していくことで、breakpoint, バックトレース等が実現できます。

フック関数方式のデバッガは、以下のような利点があります。

  • デバッガ実装のために、言語実装者側が提供するべき機能の実装負担が少ない(フック関数に関する実装のみ)
  • デバッガ実装者側は、その言語だけでデバッガ実装を行うことができる

しかし、さきほど上で述べたすべてのタイミングでフック関数が呼び出される(そして、フック関数に渡す引数の用意も毎回行われる)ため、デバッグ時はプログラムの動作がかなり遅くなります。

特にRubyでrequire等ライブラリのロードを行うと、require内部でもフック関数が呼び出されるためにとても遅いです。

動作の遅さを解消するために、Rubyのdebug.rbと違って、拡張ライブラリも用いて(C言語も用いて)デバッガを実装することによって、フック関数*4をなるべく用いない高速なデバッガを作った人もいらっしゃいます。

http://rubyforge.org/projects/ruby-debug/

少し使ってみましたが、フック関数が設定されてないうちは、バックトレースがうまく取れないようですね。

まあ、それでも十分に役に立つデバッガだと思います。

test.rb:
require 'rubygems'
require 'ruby-debug'

def hoge()
debugger
p "hoge"
end
hoge()
hoge()
$ ruby test.rb
test.rb:6 p "hoge"
(rdb:1) backtrace
--> #0 test.rb:6 in 'hoge'
(rdb:1) c
"hoge"
test.rb:6 p "hoge"
(rdb:1) backtrace
--> #0 test.rb:6 in 'hoge'
#1 test.rb:10
(rdb:1)

*1http://www.python.jp/doc/2.3.5/api/profiling.html

*2http://docs.python.org/lib/debugger-hooks.html (英語)より抜粋

*3http://www.ruby-lang.org/ja/man/?cmd=view;name=%C1%C8%A4%DF%B9%FE%A4%DF%B4%D8%BF%F4 より抜粋

*4:Kenel#set_trace_funcではなく、さらに低レベルのeval.cのrb_add_event_hookを使うようですね

デバッガの実装(Java編)

次はJavaのデバッガについて調べました。

背景

Javaプログラムの実行は、Java Virtual Machine(以下JVM)上に存在する仮想的なCPUがbytecode(仮想的なCPUが解釈する機械語)を解釈、処理をしていくことによって、行われます。

bytecodeはJavaコードをjavacでコンパイルしたときに生成されるコードでもあります。

JavaコードとCコード、bytecodeとアセンブリコードが、それぞれ似たような存在です。

OSから見た場合、JVMとJVM上で動くJavaプログラムは一つのプロセスにすぎません。

よって、OSが提供するデバッグAPIを用いたデバッガでJavaプログラムをデバッグすることが可能ですが、JVMの実行コード(アセンブリコード)やJVMが扱うデータ、JVM上で動くJavaプログラムの実行コード(bytecode)やJavaプログラムが扱うデータがごちゃごちゃしていて、デバッグするのは大変です。

JVM自身に関する情報とJavaプログラムに関する情報を切り分けて、デバッガ利用者へ提示するようにデバッガを実装すれば良いのですが、JVMの実装が変更になった時、それにあわせてデバッガを実装しなおす必要がでてきます。

また、実装の異なる複数のJVMに対応したデバッガを用意するのは困難ですし、デバッグAPIはOS依存なので、複数のOSで動作するデバッガを用意するのも困難です。

JPDAとそれを利用したデバッガ実装

そこで、Sunは、以下の3つの仕様を定めることで、JVMやOSの違いによる問題を解消しています*1

  • JVMTI(Virtual Machine Debug Interface)
    • JVMが提供するデバッグ機能の仕様
      • Javaプログラム上の変数情報の要求や、breakpointイベントの発生通知等の機能等
  • JDWP(Java Debug Wire Protocol)
    • debugeeとdebuggerでやり取りされるデバッグ情報や要求の形式に関する仕様
  • JDI(Java Debug Interface)
    • debugger側の実装に利用するpure Javaのインターフェイスに関する仕様

これら3つの仕様を総称してJPDA(Java Platform Debugger Architecture)と呼びます。

Sun自身が、各仕様を満たした、リファレンス実装を提供しているので、デバッガ製作者はJDIを利用して、主にユーザインターフェイス部分を実装するだけでデバッガが作れるようです。

また、JVMの実装者は、JVMTIの仕様を満たすようにJVMを実装し、JDWPとJDIに関する実装はSunのリファレンス実装を利用すれば、新しく実装したJVM上で動作するJavaプログラムのデバッグを、既存のデバッガで行うことができるんでしょう(たぶん)。

メモ

  • JPDAに関するドキュメント

http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/guide/jpda/index.html

  • Java Debugger
    • CUIベース
      • jdb
      • jdebug
    • GUIベース
      • jswat
  • JVMの種類
    • Sun JVM
    • IBM JVM
    • WebLogic JRockit JVM
    • Microsoft JVM

*1:Java2 sdk 1.4時点