いまどきのUNIXプログラミング

久々にblog更新しようとしたら、UIが一新されててビックリ。

さて、しばらく前の話になりますが、やや若い世代の人と集中的に開発を行う機会がありまして。「epoll使っていいですか、selectってあまり使った事ないので」と言われて愕然。当たり前と言えば当たり前なんだけど、90年代に身に着けたUNIXの知識もいまや年代物。少しはアップデートしないとなぁ・・・という事で本を読んで勉強したので、そのメモ。もしろん昔からあるけど知らなかったって事も沢山ありました。

読んだのは「LINUXシステムプログラミング」というO'REILLY本。400ページ弱という（この手の本にしては）薄い本なのだけど、興味深い話題が多く楽しんで読めました。以下、この本によってアップデートされた私の知識の項目一覧と概説。これを見て「おぉ」と思った人は仲間なので買って損はないと思う。

ファイル・I/O

ノンブロッキングI/O

O_NONBLOCKによるノンブロッキングI/O。知らなかったわけじゃないけど、自分のアプリでは使った事なかった。

同期I/O、ダイレクトI/O

fsync()とfdatasync()。あと、O_SYNC、O_DSYNC、O_RSYNCとか。O_DIRECTも。

ファイルサイズを超えたシーク

あぁ、これやるだけでsparse file作れたんだ・・・知らなかった。

ファイルポジション指定I/O

pread()、pwrite()とか。これはqemuの移植やってた時に見かけたのでちょっと前から知ってた。PepperのFileIOってpread()/pwrite()系列のAPIになってますね。

I/Oの多重化

select()ループがクールだった時代はとっくに終わってた。シグナルハンドラでできるのはpipeに書いてselectを起こす事くらい・・・と信じてた人はpselect()を調べるべし。あと知らなかったけどSystem V系ではpoll()とかppoll()というのがある。でも、今時Linuxでサーバ書くなら大量のデスクリプタに対してもスケールするepoll_*系関数群を使うべき。期待した通りのインタフェースを持ってる。Win32のWaitForMultipleObjectsより賢い多重化が可能になったと思う。

scatter-gather I/O

readv()とwritev()。リンクアレイチェーン転送的なI/Oインタフェースと言えば一部の人には分かりやすいかも。

ページサイズ取得

普段みかけるのはgetpagesize()ばかりなんだけど、こっちはLinux固有で、POSIX的にはsysconf(_SC_PAGESIZE)が正しいらしい。確かにNative Clientもsysconf()は持ってる。

I/Oスケジューラ

Deadline I/Oスケジューラ、Anticipatory I/Oスケジューラ、CFQ I/Oスケジューラ、Noop I/Oスケジューラ。4.6節でいきなりOSの教科書かと思うような細かいスケジューラの解説があります。なんでかと思ったら、Linuxは手軽にI/Oスケジューラが差し替えられるんですね。この辺は純粋なOS好きにとっても楽しめる内容かと。

拡張属性

xattr。時代はレジストリ、もといBFS。

ファイルイベント

inotify_*系のインタフェース。さらば、SIGHUP。

プロセス管理

プロセス階層

あんまり真面目に見て来なかったプロセスグループの話。

ゾンビプロセス

そういえば、なんでプロセス終了時に子プロセスを回収する処理をOSレベルで走らせないんだろ。ゾンビとして生かしておく根拠を知らないなぁ・・・。wait系は直接の子供しか待てないという理解なのだけど。

ユーザとグループ

プロセスのユーザIDは、実ユーザID、実効ユーザID、savedユーザIDの3種類ある・・・知らなかったし、一度読んだだけでは覚えられない・・・。

セッションとプロセスグループ

シェル書いてジョブコントロールとかしようとすると必要になる知識なんだろうけど。そう言えば、ちょっと前にLinuxに入ったスケジューラの改善って、この辺をうまく考慮してスケジューリングするとかなかったっけ？

※記憶と照合するとStaircase Schedulerの事だったのかなぁ・・・。でも、それももうobsoleteっぽい。ちなみに「Linux カーネル 2.6 Completely Fair Scheduler の内側」はスケジューラに関する良い記事な気がする。

デーモン

日頃お世話になっているdaemonさん。実は然るべき正規の手順が存在していたのですね・・・。新規プロセスグループのリーダープロセスにした上でchdir('/')して標準入出力は全て/dev/nullにする。わりと面倒な処理が必要みたいだけど、実はdaemon()ってライブラリ関数がある・・・というのも知らなかった。

I/Oの優先度

プロセス優先度だけでなく、ioprio_get()/ioprio_set()というインタフェースでプロセスのI/O優先度を指定できるらしい。ただしCFQ I/Oスケジューラ選択時に限る、か。

プロセッサアフィニティ

sched_getaffinity()とsched_setaffinity()。なるほど、SunOS+Oracle以外でも今や当たり前のインタフェース。

名前空間

Linuxでは（ファイルシステムの）名前空間はシステム固有ではなくプロセス固有。古典的なUNIXではシステム固有。Plan 9由来ですね。逆に、これがないとchrootってどうしてるんだろ。単にアクセス範囲をサブツリーに限定してるだけ？

メモリ管理

アラインメント

posix_memalign()。

/dev/zeroのmmap

そう言えば、そんなテクニックもあった。

高度なメモリ割り当て

mallopt()、malloc_usable_size()、malloc_trim()、mallinfo()あたりは知っていると使う機会もありそう。

スタック上への文字列コピー

strdupa() = alloca() + strdup()。C言語だけで開発する機会ってのも無くなってきてるので、知ってて役に立つかは微妙だけど。

ピンダウン

mlock()、mlockall()、munlock()、munlockall()。mincore()でスワップ判定。

オーバコミットとOOM

OOM Killerとの付き合い方。そういえば青山Killer物語の舞台って青山キラー通り？

シグナル

「古い実装ではシグナルを喪失することがありました。」いえ、それは私が知っているシグナルの実装、そのものです・・・。古い実装ではシグナル送信はプロセスにただ１つ存在するバッファにシグナル情報を保存して戻るだけの単純な実装で、プロセスは起きる前にバッファを確認し、存在していれば最新のただ１つのシグナルを処理してました。ところが、今時のシグナルを考えると、他にも考えなければならない問題が。

例えば、この本にも載ってなかったけど、マルチスレッド環境でシグナルを処理するのは誰（どのスレッド）か。答えは任意のスレッド。具体的な実装を見たわけではないけど、シグナルが積まれた後、最初に起こすスレッドが処理するのが一番ナイーブな実装か。特定のスレッドで受けたければ、他のスレッドはシグナルマスクを設定するのが作法らしい。

時間

時刻表現

micro秒のtimevalとnano秒のtimespec。最近はnano系が標準化されてるので、timespec系に一本化しとくと間違いなさそう。

POSIXクロック

clock_gettime()。Native Client内でも動いてるので重宝してます。

スリープ

秒単位のsleep()、micro秒単位のselect()ってのが古典の世界。今はmicro秒単位のusleep()もあるけど、nano秒単位のnanosleep()、clock_nanosleep()が標準化の観点からもオススメらしい。

タイマー

POSIXクロックの一部。time_*系関数群。

と、まぁ、こんな感じです。この本には出て来なかったけど、ttyとかも深い闇なんだよなぁ。未だに理解しきれてないプロセスグループやネットワークスタックなんかの話も含めて、いずれBSD本あたりを熟読したい次第。

 

安価な自作USBを作ってみる

VUSBを使った自作USBデバイスを作ってみたら、思った以上に簡単だったのでご紹介。

今まで自作USBデバイスと言うと、PIC18F2550を使ってました。これ自体は350円と安いのですが、標準フレームワークが純正C18専用ってとこが微妙。自分はSDCC向けにフルスクラッチでUSBスタック書いてたけど、USB関連のレジスタは簡単なビットフィールドの説明以外、詳しい触り方の情報がないので・・・まぁ普通はしないですね。

で、電子工作屋さんとしてもう一つ選択しに出てくるのがAVRシリーズ+VUSBという選択。こっちはハード的にはTINY2313でも動かせるので石の値段はたった100円で済む。ただし、ソフトウェア的にUSBの物理層を話そうとするので、USB 1.1 low-speedまでが限界。と言っても、自作レベルでそれ以上の転送レートが必要になるようなデバイスを作る事はそうそうないので、まずは用が足ります。

という事で、今回はVUSBの調査も兼ねてAVRで作ってみる事にしました。周辺に必要な素子は、自分の場合、回路箱から適当に見繕ってるんだけど。個別で集めるとなんだかんだで300円くらいになっちゃうのかなぁ。基板とUSBの端子、セラロック、4.7uの電解コンデンサ。あと抵抗とパスコンを少々。最後に3.3Vを作るためのお好みの回路。自分の場合、HIDaspx自作する時によくやってたのが、USBバスの5Vから電源用LEBを差して電圧降下で3.3Vを狙う方法。多少ずれても平気だけどホスト側との相性が出やすい、電圧が不安定になりがちでコンデンサで調整しないと動かない事も多々あり、たまにLEDが過負荷で飛ぶ・・・みたいな感じであまりオススメできません。今回はツェナーダイオードを使う方法で、2個直列させて安定3.3Vを作りました。ツェナー使ったことない人は向きを間違えないように注意。この辺りはチップが3.3Vを作ってくれるPIC18F2550のほうが圧倒的に楽で安心。

回路を作る上で注意しないといけないのは、リファレンス回路のままだと割り込みピンが全部持ってかれちゃうのとクロック出力が使えない、という2点。もしどちらかが使いたければ、ピン配置を変える必要ありです。ファーム側の変更は後述しますが、とても簡単なので遠慮なく変えちゃってOK。ただし、最低でもD+は割り込みピンに繋ぐ必要がある点だけ注意。ファームはD+のエッジをトリガにして割り込みで起動、クロックを数えながら物理信号を読み解くのです。同じくVUSBを使ってるHIDaspxなんかは、クロック出すためにピン配置変えてますので、回路のテスト用にとりあえずHIDaspxのファームを・・・という時には注意が必要。はまります（と言うか、はまりました）。特にヒューズの値が違うという点を忘れがち。

VUSBを使いながら、どれくらい自由にファームが組めるのか、という点が気になる所かと思います。前述の通り、物理信号の読み取りに割り込みハンドラが1つ取られます。あとは50msecに1回以上の頻度でusbPoll()を呼んであげればOK。usbPoll()の中では、割り込み側でパケットを検出していればホストからの要求を見て自動的に応答、あるいはユーザハンドラを起動して、ユーザからの応答を送り返す、といった処理をしてくれます。物理層読み取りと50msecの話があるので、リアルタイム制約の厳しい処理は共存できません。例えばソフトウェアUARTとかソフトウェアNTSC/VGAは書けないし、タイマー割り込みでPWM使って波形合成、みたいなのも安定させるのは難しそう。そういう時はもう1個マイコンを用意して、そっちでリアルタイム処理。チップ間はタイミング制約の緩いコマンドのやり取りで片付ける必要があります。

実際のファームの作成ですが、example以下にサンプルがあるので倣って作ればOK。USBのプロトコル知らなくても書けるレベルじゃないかな、これ。非常に簡単。ドライバ作らなくても良いって理由でHIDクラスのデバイスとして作る人は多いみたいなんだけど、自分はお気楽ドライバで好き勝手できるという点から、むしろカスタムクラスで作っちゃってます。
usbconfig.hというのがデバイスデスクリプタやピン配置を定義してるファイルで、マクロの値を説明に従って書き換えていけばOK。自分の時の書き換え例をここでdiffで見えるようにしてあります。D-のピン番号変えて、あとは要求電流を規約上最大の500mAにしてます。自作デバイスの消費電力とか、まず正確に把握するのは無理なので、とりあえず最大値を言っときましょう的な。実はMac使ってると、ここで宣言した以上の電力を使った時に「このデバイスの電力消費は多すぎ」みたいな警告ダイアログが出て、デバイスを無効化してくれます。ので、怒られたら増やして、みたいな対応もアリです。ベンダー/デバイスIDは個人で使ってる分には適当に。正規ID取得は結構お金かかるんだけど0x6666がPrototype product Vendor IDにアサインされてるんで、自分はこの値を使ってます。main処理はこんな感じ。usbInit()呼んだあとにusbDisconnect()状態で100msec以上待機、usbConnect()を呼んでからusbPoll()のループに入ってます。

プロトコル処理も今回は一番安易な方法。新規のエンドポイントを作らずに、デフォルトパイプでコントロール転送だけ使ってデバイス制御させてます。さっきのmain.cの中のusbFunctionSetupとlinux用ドライバのcrts_set() /crts_get()あたりを見比べてもらえば簡単に理解できると思います。

あとはMakefileの中で使ってるクロックを指定してやる必要があります。自分は20MHz使ってます。クロックによって物理層を読むときの遅延コードが変わるので、コードサイズにも若干影響します。他のクロックのほうが小さくなるって話を見たような気もしたんだけど、今手元で試した限りでは20MHzが一番小さくなってます。その他のファイルも合わせGoogle Codeに上げてあるので試しに何か作ってみようという方は参考にどうぞ。

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.

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.

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

久々に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

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状態がデバイスの実時間をシミュレートしているためではないかと思います。