2011年9月23日金曜日

Memo to build official android emulator

This is a memo to build official android emulator which Android SDK includes. This emulator forked from qemu.

Get source codes
$ cd $WORK
$ git clone git://codeaurora.org/platform/external/qemu.git
Build
$ cd $WORK/qemu
$ git checkout origin/aosp/tools_r13
$ ./android-configure.sh
$ make
Prepare OS images
$ cd $WORK
$ wget http://dl.google.com/android/android-sdk_r13-linux_x86.tgz
$ tar zxf android-sdk_r13-linux_x86.tgz
$ cd android-sdk-linux_x86/
$ ./tools/android
(Install SDK platform packages, then create virtual machine definition named X in GUI. Android 1.6, 2.3.3, and 3.2 will work fine.)
Launch the OS image
$ ANDROID_SDK_ROOT=$WORK/android-sdk-linux_x86 $WORK/qemu/objs/emulator-arm @X
(X is the name you named in preparing OS images.)
Memos

  • codeaurora.org is an unofficial mirror repository. If kernel.org come back, you must use the git://android.kernel.org repository.
  • If you'd like to build on OS X, you must build in a case-sensitive file system because block.h conflicts with system provided Block.h. Default file system is case-*in*sensitive, so you may prepare a disk image and work in it as follows;
    • $ hdiutil create $NAME -size 1024m -fs HFSX -volume $VOLUME; hdiutil attach $NAME; cd /Volumes/$VOLUME; do something...
  • If you'd like to build trunk sources, you may want to use prebuilt SDL library in /platform/prebuilt.git. It could be passed via --sdl-config arguments in android-configure.sh. But I guess it miss three functions including SDL_WM_GetPos, etc. Also it will be a pretty tough and boring work to find some stable combinations between versions of SDL, qemu, and OS images.

2011年9月19日月曜日

CPU Emulation using JIT on JavaScript

I'm struck with an idea to implement CPU emulation using JIT like technique on JavaScript. Basically, the emulator generates JavaScript function which emulate a target binary sequence by the basic block, then cache it in hash. The code could be like 'cache[pc] = eval(jit()); cache[pc]();'.

Since I'd like to know how this technique could be effective, I just make a tiny pseudo emulator and estimate its performance. The result show the JavaScript CPU interpretor will be x100 slower than a native code. Modern JavaScript engines become faster and faster. But it seems to be still slow. On the other hand, qemu-arm seems to be quite fast. It's just several times slower than the native one. So how about my emulation using JIT on JavaScript? It's slower than qemu. But not so bad. It might be pretty fast than native CPU interpreter.

As supplements, I must say that this benchmark treats just one simple case and the result will be changed by loop size, count, and JIT overheads in various situations.

2011年9月14日水曜日

g++ bit-fieldsの謎

C++でbit field使ってるコードでハマった。
擬似的に書くと以下のようなクラス。

class A {
  signed a: 15;
  signed b: 15;
  bool c: 1;
  bool d: 1;
  void *e;
};

んで、Vector<A>を比較するのに、性能を気にしてsizeof(A)*lengthでmemcmp。
x86やARMでは問題ないんだけど、x86_64になると問題発生。
実質12Bのペイロードに対して、sizeof(A)が16。
全フィールドを初期化しても未初期化領域が必ず残ってしまうという罠。
ポインタがいるから8Bに揃えてるんだろな、と思ってポインタを頭に持って行っても結果はかわらず。
x86_64 ABI的には構造体は8Bアライメントなのか。。。
ということで、memcmpでは不一致が発生してしまう。
ちなみに32bit環境ではsizeof(A)は8でびっしり詰まってる感じ。

その後、色々試しているうちに気づいたんだけど、
bit-fieldが15,15,1,1の組み合わせだと詰め込んで32bitに納めてくれるんだけど、
31,31,1,1の組み合わせだと64bitに詰め込んでくれない。
けど、31,1,31,1の順に並び替えれば64bitに納めてくれる。。。どんな規約なんだ?

・・・と、そうこうしてたら@nminoru氏のABI仕様の指摘。
出てきた順にLSBから32bit単位で詰めてく模様。
はみ出そうになったらパディングして次のアライメントから。
なので、15,15,1,1の組み合わせは(15+1)x2になってるわけじゃなく、
[14:0], [29:15], [30] [31]というマップになるようだ。
だから、31,31,1,1の場合は、31,31+1,1となって、31,1,31,1の場合は(31+1)x2。
うん、納得だ。__attribute__((packed))がbit-fieldに対しても効果があることも、
32bit単位のアライメントを無効化してくれると思えば納得なのであった。

という事で、もっと仕様をちゃんと読め的な、いつもどおりの教訓を胸に抱きつつ、次号にコンティニュー。

参考)
IA-32 ABI : http://www.sco.com/developers/devspecs/abi386-4.pdf#page=33
x86_64 ABI: http://www.x86-64.org/documentation/abi.pdf#page=14

2011年4月13日水曜日

久々にCPU関連のサーベイ - Survey on CPU Top Conference

ひとまず去年のISCA、MICROで面白そうな論文ないかなー、ということで選ぶだけ選んでみた。まだ読んでないので、すでに読んだという人がいたら教えてくれると嬉しいです。
For the time being, I took a glance at the last ISCA and MICRO to catch up. I just choosed interesting papers and not already read. If you know following papers, please  teach me the essence :-)

分野的にも興味あって面白そうなやつ。
Papers which I'm interested in and on which I would like to research.

ISCA 2010
 - Translation Caching: Skip, Don't Walk (the Page Table)
 - NoHype: Virtualized Cloud Infrastructure without the Virtualization

MICRO 2010
 - Architectural Support for Fair Reader-Writer Locking

少なくとも当面は手を出しそうにないけど面白そうなやつ。
Papers being interesting, but I wouldn't start on just yet.

ISCA 2010
 - High Performance Cache Replacement using Re-Reference Interval Prediction (RRIP)
 - The Virtual Write Queue: Coordinating DRAM and Last-Level Cache Policies
 - Morphable Memory System: A Robust Architecture for Exploiting Multi-Level Phase Change Memories

MICRO 2010
 - Synergistic TLBs for High Performance Address Translation in Chip Multiprocessors
 - ASF: AMD64 Extension for Lock-free Data Structure and Transactional Memory

2011年4月12日火曜日

Lions' Commentary (11) - 読書会#6 -

再び読書会の記録です。
今回は13章・・・の途中まででした。signalの処理全般とexit、waitの関係あたりなので内容としては重たかった。ので、仕方ないかなぁ、という感じですね。トレースの部分が終わらずに次回へ繰越です。

ssig
Lions本では3625行について明確な答えが得られていない。自分の理解を読書会で話したんだけど、たぶん同意してもらえたと思う。つまり、あるシグナルハンドラを設定する際、その設定よりも前に該当シグナルが発生し、処理待ち状態になっていたならば、新たなハンドラはその過去に発生したシグナルに関して興味を持っていないはず。よって、なかった事にして良い。もちろん丁寧に処理するのであれば、古いハンドラを呼び出してあげれば良いわけだが、例によってコンテキストスイッチのネストは複雑なので、処理せずに済むのであれば処理しないのがベター。もともとKILL以外は最新のシグナル以外は上書きロストする仕様なので、ここは手を抜くのが落とし所として適切。

kill
pidに0を指定して呼び出した時の動作が特殊。今時のUNIXではこの時、呼び出し元プロセスと同group IDを持つプロセス全てにsignalをbroadcastするのが仕様。当時はまだgroup IDの概念がなく、同じttyにぶら下がっているプロセス全てにbroadcastしている。端末でコントロールコードを入力してsignalを飛ばすとき、この機構を使うのが一般的と思われる。

psignal
シグナルハンドラの起動。kill経由で呼び出されるがLions本で指摘?の通り、バグ持ちのようだ。signal番号として負の値を入れて呼び出すと、psigで配列の範囲外を読み出し、ゴミデータをハンドラのアドレスだと思ってハンドラ呼び出しをしてしまう。たぶんOSごと死んでしまうのではなかろうか。
さらに言えば、シグナル番号が範囲外だった時にエラーを返さない。本来ならssig同様に範囲チェックをしてエラーを返すべき。

issig
トレースが有効になっていたらstopを呼び出す。さらにstopでは親プロセスIDが1だった場合(initの子供だった場合)にプロセスを終了する。ここだけ読んでもわからないが、これはプロセスのデバッグ中に親のデバッガプロセスが不正終了した時のためのコード。親が先に死んだ場合、子プロセスはinitの子プロセスとして登録されるというのがUNIXの風習。initがデバッガの代理処理を行うわけにもいかないので、諦めてデバッガプロセスと道連れでデバッグ対象プロセスもexit・・・、というのはやむを得ない処置か。

exit
user構造体の複製をswap領域に作成し、終了コードを保存。全シグナルハンドラを無視に設定して、プロセス領域を開放、ゾンビプロセスになる。その後の処理が読書会の中でも時間をかけて議論された部分。
まず、親プロセスが存在しないと、自分自身をinitプロセスの子プロセスとして登録する。続けて、initプロセスと親プロセスを起こす。最後に未回収の子プロセスをinitプロセスにぶら下げ直して、コンテキストスイッチ。initプロセスを起こすのは、initにぶら下げた子プロセスが既にexitしてwait待ちになっている可能性があるため。親プロセスを起こすのは、自身の終了をwaitで待ってブロックしている時のため。全者の理由を解読するのに時間がかかった。
プロセスを起こす処理はwakeup(&proc[1])とwakeup(p)。waitで寝るとき、自身のproc構造体のポインタが要因として利用されるため、このような記述でそれぞれwait中のinitプロセス、親プロセスを起こすことになる。

wait
ゾンビ化したプロセスを最終的に回収して上げるのがwait。UNIXではfork、execで生成されたプロセスは、exitで実行イメージを開放し、終了コードを含むuser構造体をswap領域に退避する。最後に親がwaitで回収する事でuser構造体を含む全てのプロセスリソースが開放可能となる。逆に言えば親のwaitで回収されないプロセスはゾンビプロセスとして永久にswap領域内に居残り続ける。PDP-7 UNIXの頃はこのあたりの終了コードのやり時も、もう少し汎用性の高いプロセス間通信で行われていた模様。ところが、実際には決まりきった使い方しかされていなかったので、マルチプログラミングの改善時に、終了コードの受け渡しだけに特化したexit、waitの実装になった模様。このあたりの様子はUNIX原典に書かれてます。

7shiさんのデモ
いや、これは熱い。デモを見せてもらったんだけど、Silverlightのファンになりました(言い過ぎ)。しかし、良く作りこまれていて。Ken Thompsonとかが見たら泣いて喜ぶんじゃないだろうか。コマンドライン版はbinfmt_miscに登録すると素敵かもしれない。あとqemuにマージされたりすると、もっと素敵。
そうそう、simh上の動作は標準出力が遅い〜みたいな話があったけど、たぶんコンソールから出力するにあたり、kl.cのドライバ経由でtty.cのコードが動き、デバイスのBUSY状態を見ながら出力している&BUSY状態がデバイスの実時間をシミュレートしているためではないかと思います。

2011年3月28日月曜日

Lions' Commentary (10) - 読書会#5 -

読書会、#1と#2に参加したけど、#2は怠慢により日記更新なし。#3と#4は都合により不参加・・・という事で、久々の参加記録になります。綺麗にまとめようとして更新できなくなるのも残念なので、乱文ですが更新させて頂きます。

さて、今回は第12章と第13章がテーマの予定だったのですが・・・内容が重かったため、第12章だけをみっちり半日議論、って感じになりました。第12章だけと言っても、trap内でハードウェア例外からsignalを設定、システムコール呼び出しの場合はエントリテーブルを引いて各システムコールの実装の呼び出し、といった重たい内容からスタート。続けてシステムコールの実装の中から、execとfork、sbreak。UNIXの魂とも言えるAPI群を読み解くことになるので、かなり難解。章の最後にはさらっと「ここは自分で読んどいてね(はーと)」ってノリで12のシスターならぬシステムコールが。。。とりあえず、自力で読んだ時には気づかなかっけど、読書会でみんなで議論したら気づいた、理解できた、って事を重点的に書き出そうと思います。

trap
SETD(擬似?)命令を踏んでIllegal Instructionが発生した場合は無視となっているが、カーネルだけ読んでいるとこの辺のユースケースが理解できず。FPU周りでCコンパイラが自動挿入するんだろう事はコメントから想像できますが、何事もなかったかのように処理されるため、例外起きたか否かでFPUの何らかの機能の有無を判定、ってわけでもなさそう。この部分は今回解明できなかった点の1つ。
次はLions本でも指摘されてるcase 8とcase 8+USERでのfloating exceptionの処理の違い。8(kernel)だとsignalセットしたら該当プロセスを起こすだけでuser modeにreturnしているけど、8+USERの場合にはsignalセット後にハンドラを起動している。system call呼び出しやsignalハンドラ起動用のr5,r6保存場所が、スタック構造ではなく固定箇所への退避になっており、多重呼出しに対応できないから、という解釈。つまり、kernelからtrapが呼ばれてsignalをセットしてハンドラ起動〜ってパスで動作させようとすると、戻る時にkernelより前に正しく戻せないパタンが出てくると思っています。
ちなみにkernelモードでfloating exceptionが起きるのは、kernelでFPU使ってるわけではなく、PDP-11が正確な例外をサポートできておらず、例外が数命令滑ってからトラップされるため。backup()付近を読むと、PDP-11は正確な例外(precise exception)が実現できていなかった事がわかり、今時のCPU屋さんとしてはアンモナイトを見たような衝撃を受けるわけです。
system call((*f)())直前にu_qsavにr5,r6を退避している点の理解もやや不完全。u_qsavからの復帰はsleep内だけ、というのは簡単に調べられるので、sleep呼ぼうとした時に、わきからsignalが飛んできた時の対策かな・・・とは想像されるのですが。sslepのwhile文から大域脱出したいためだけに使ってる?
間接呼び出しについても話題になりました。通常の仕組みだと引数を含めたシステムコール呼び出しのコード全体が静的にテキスト領域に埋め込まれる形になるので、動的なシステムコール呼び出しができない。このために間接呼び出しの仕組みが用意されていて、システムコール0番を呼び、第一引数にポインタを設定すると、ポインタの先のデータ領域をシステムコール(trap命令+コール番号)と引数の構造だと解釈してシステムコールを間接実行する事ができる。実際にv6のlibcのwriteで使われてるよ、とかいう話がありました。
アセンブラで書くとこんな感じ?
.text
direct_call:
    sys write
    hello
    6
hello:
    <hello¥n>

.text
indirect_call:
    sys indir
    entry
.data
entry
    sys write
    hello
    6
hello:
    <hello¥n>
exec
execは先の知識がないとblack boxとして読み飛ばさないといけない関数がぼちぼちあって気持ち悪い。nameiはファイル名からinode構造体へのポインタを求める関数、getblkは、もともとI/Oのブロックバッファ(ディスクキャッシュ)を検索してバッファを引っ張ってくる関数だけど、ここではNODEVを対象とした特殊処理で、空の新規ブロックバッファ512Bを取得するために使っている。
nameiとuchar周りが気持ち悪くて、system callから渡されたファイル名がどうnameiに渡っているのかを理解するのが結構大変。というか実装が汚い。ファイル名はr0決め打ちでsystem callに渡される事になっていて、trap()、u.u_dirp = u.u_arg[0]の形でu_dirpにr0のポインタがコピーされる。uchar()ではこのu_dirpを決め打ち引数にして文字列をuser空間からkernel空間にコピーしており、これがnameiに渡るファイル名になっていく・・・というのが大まかな流れ。
a.outのフォーマットについては410形式ではテキスト領域がページ単位でパディングされており、read onlyで複数のプロセスで共有できるようになっている、との事でした。
u.u_prof[3] = 0;は宿題。profil()でプロファイラを有効にしていると、ここが非0になっていてclock()でプロファイラが動くことまでは追えている。けど、なぜテキスト領域開放直前に0クリアしてるのかまでは理解できていない。
データセグメントのロード部分はややトリッキー。MMUを書き換えて0番地にデータセグメントをマップ、readiで0番地以降に直接転送をして、終了後にMMUを元に戻してる。機能的、あるいは性能的に意味のあるトリックなのかが理解できていない。
ISUID関連も少し勉強不足。非rootプロセスだった場合でISUIDが立ってた場合はファイルのuidに権限を移行してから実行開始。非root→rootは遷移できるのに、root→非rootは遷移できない。そういうもの?
最後にちょっと衝撃だったのがシグナルハンドラ周り。シグナルハンドラはu_signal[]にsignal毎に格納されており、0がSIG_DFL相当、奇数(主に1)がSIG_IGN相当で、偶数(validなポインタ)が通常のハンドラ、という割り当て。exec字には偶数のエントリだけ0に初期化、という事をやっているので、どうやらSIG_IGNの設定は子プロセスにも継承される仕組みらしい。これは現在のPOSIXでもこういう仕様?

fork
system callレベルでは親に子プロセスIDが返るだけじゃなく、子プロセスにも親プロセスIDが返る(少なくともいまどきのC言語レベルでは子プロセスには0が返る)というのが、ちょっと新鮮だったわけですが、自分の理解はそこまでで、最後のu_ar0[R7] += 2; つまりプログラムカウンタの更新の意味は理解できていませんでした。他のsystem callについてはtrap内でエントリ構造体を引いて引数の数だけカウンタを回していたので、forkだけ特殊なのが理解できませんでした。が、ここで青柳くんのヘルプ。どうやら、forkから返ると親プロセス側では後続の1命令をスキップする、という仕様らしい!!!これはわりと衝撃。というか、醜い実装? 何か歴史的な背景があるのかなぁ。forkだけにfork内でパスが分岐して返ってくるほうが当時の人の直感と合ってたんでしょうか。

sbreak
セグメントごとのサイズを足し引きして、データセグメント部のサイズを変更するだけの機能。面倒なだけで、あまり難解なところはないのですが・・・自分的にはsbreakという名前がUNIX触り始めた頃からの長年の疑問でした。sbrkという関数名を先に知っていて、brkってなんだろう?breakじゃないよなぁ・・・と思ってたんですが、やっぱりbreakでした。コメントにもbad planningとか書いてあるし、命名に失敗したようです(Cのbreakが失敗なのか、sbreakが失敗なのかは不明)。ここで参加メンバーからmanの紹介があり、manを読んでいて名前の由来に気づきました。どうやら、スタック先頭(=プロセスが使っているメモリ空間の末尾)をbreak pointと呼んでいるらしい。sbreakはset break pointの意味? メモリ空間の中でここまでvalid、という意味でいうなら、このbreak pointという意味合いもなんとなく納得できますし、ひょっとしたらMMU以前から使われている名前なのかなぁ、という気もしてきます。MMUのない世界ではプロセス境界ですよね、このbreak pointの場所って。DOS(というかhuman68kの頃の記憶)だとプロセス起動時に空きメモリ全てが渡されるので、子プロセスを呼ぶ際には必要最低限にsbreak相当で切り詰めてから子プロセス起動、ってやってた気がします。なんか共通の根っこでもあるのだろうか?

という事で、新たに発見した事をまとめたつもりだったのですが、改めて読むと分からなかった事リスト、宿題リストになってますね。。。まぁ、それだけ難しかったという事で。