Boot to CP/M

今更なんですけどね、UEFIを触ってみましたよ。
昔AVR用に作ったCP/MエミュレータをUEFI for x86_64向けに改造して、OS無しで直接CP/Mがbootできるようにしてみました。

Ubuntuだったら以下の手順でbuildできます。

% git clone https://github.com/toyoshim/cp-mega88.git
% cd cp-mega88
% sudo apt-get install gnu-efi
% make -f Makefile.uefi

でcpmega88.efiってファイルが出来るので、EFIのパーティションにEFI/Boot/bootx64.efiって名前でコピーするか、EFI Shellから起動するかでCP/Mが起動します。CP/M用のディスクイメージはEFI/cpmega88/sdcard.imgって名前で用意してください。githubのページで詳しく書いてますが、z80pack用のイメージがそのまま使えます。

QEMUが入ってれば以下の手順でも動作確認できます。

% make -f Makefile.uefi install
% qemu-system-x86_64 -bios OVMF.fd -hda fat:.

OVMF.fdはこの辺から入手できます。

USBメモリとかに入れておけば、UEFI対応のPCに挿して起動するだけでCP/Mが動作します。わー、嬉しい！

いまどきの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本あたりを熟読したい次第。

 

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相当で切り詰めてから子プロセス起動、ってやってた気がします。なんか共通の根っこでもあるのだろうか？

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

近況2010！

だいぶ前に仕事が一段落したので同人を・・・みたいな事を書いたのですが。
やはりどこかにボトルネックがある限り、手が空くって事は許されないのですね。
あまりにも非生産的な毎日になってしまったので、意を決して今月転職しました。
そんなわけで、生活の根っこはだいぶ改善されたような気がします。

転職に至るまで、外の世界にも目を向けようと、前回のblogに書いたイベント参加。
あるいは最近はやりの勉強会なんてのにも顔を出すようになりました。
最近ではカーネル／VM探検隊、Lions' Commentary on UNIX読書会なぞに参加して、
結構良い刺激になるとともに、ストレス解消にもなってます。

カーネル／VM探検隊向けにはHaiku OS向けのyurexドライバを書いたりしたので
次回参加時には軽く紹介したいなぁ、などと思ってます。
BeOSの系譜らしく、Pulseで貧乏揺すりの度合いを見える化できます！

Lions'本については昨年から独りで細々と読み進めており、最近になって
元会社の同僚を説き伏せて、内輪で盛り上がりつつあったところでした。
まさか大人数で集まってわいわいできるとは思っていなかったので嬉しい！

あと、ここ数年自宅サーバのマシンやHDDが壊れる壊れる。。。
という事で、だいぶカオスな状態で放置されていたサーバ群。
仮想化や冗長化をすすめ、だいぶ快適さが向上しました。

加えて買ったきりでセットアップもままならなかったmotif-rack xs。
こいつもLogicとCubaseからストレスなく使える環境が整った！
だいぶ遅れて迷惑をかけてしまってるんですが、Doll's Ingramの曲は
この環境を使って作曲作業を再開しています。

rackはYAMAHAが音色定義を配ってないので、motifの設定を流用。
あと、Logic用は面倒な手順が色々と書かれてるんだけど、裏技的な方法として、
エンバイロメントのウィンドウを開き、レイヤーとしてテンプレートファイルを開く、
とかやると便利です。
テンプレートから設定をコピペしたり、作業をテンプレートから開始したり、
とかいう煩わしさ、制約から解放されます。

The Singularity System

ここのところ、まったく時間がなかったのですが、出張帰りの飛行機で時間があったので、Communications of the ACMに寄稿されていたSingularityの記事を読んでみました。

SingularityとはMicrosoft Researchによる研究段階のOperating Systemです。micro kernelを採用しており、コストの高いプロセス間通信を解決する方法としてSIPと呼ばれる機構と、高位言語による記述を採用している点が特徴かと思います。

大雑把な説明はWikipediaの解説が手っ取り早いでしょうか。

Singularityでは、OSを含めて高位言語で記述するのが基本です。kernel本体はSing#と呼ばれるC#の拡張言語で記述され、他にはC#、F#、Visual Basicあたりがサポートされています。

Wikipediaを見るとSIPはmicro kernelと各サーバ群との通信を最適化するための仕組みのようにも見えますが、記事によるともっと一般的なプロセス分離の仕組みのようです。

Singularityにおけるプロセス保護は多層で実現（multiple layers of protection）され、基本的な方式がSIP、二次的な方式が仮想メモリ空間による分離（近代的なOSが一般的に採用している方法）になります。

SIPによる分離では、同一メモリ空間内にページ単位で複数プロセスを貼り付け、仮想メモリ空間切り替えによるプロセス切り替えコストを除去する事が目的となっています。ページ保護は利用しているようなので、SIPで分離されたプロセス間の切り替えでは、ページのアクセス権限だけ書き換えるのかな？この辺は詳しく書かれていないので想像です。このへんの保護は言語レベルでのサポートや形式検証なども使えるみたいです。

一般的にプロセス単位で仮想メモリ空間を切り替えるメリットは、メモリ保護だけでなくメモリ管理にもあります。プロセスにつきヒープとスタックという二種類の可変長作業域が必要となります。一般的にはヒープは下位アドレスからプラス方向に、スタックは上位アドレスからマイナス方向に伸びていくことで実現していますが、同じアドレス空間に複数のプロセスを配置するとなると、ヒープを拡張しようとしたら、別のプロセス空間が邪魔で・・・なんて状況が起き得ます。

680x0時代のMac OSでは、MMUが使えなかったため、ハンドルとコンパクションという考え方で対応してきました。メモリはハンドルで管理し、必要なときだけロックをかけてハンドルからポインタに変換します。使い終わったメモリはすぐにアンロックすることで、ポインタは無効になります。このお約束を守ることで、連続したメモリ領域がなくなった時、コンパクションによってロックされていないメモリを移動し、メモリ再配置による最適化を行うことができるようになります。

Singularityでこの辺りをどう対処しているのかは読み取れませんでした。Garbage Collectionによるメモリ管理をOS含めて導入しており、runtimeによるポインタチェックも行っているようなので、その気になればコンパクションもできるのかもしれません。今時のメモリサイズであれば、コンパクションがなくて実用上問題にならないのかなぁ。

あるいは、記事の例を見ると、そうは言ってもSIPによる分離は共有ライブラリやコンポーネント、Plug-insなどのレベルでメモリ保護を実現するための機構として利用しているようにも見え、実際には仮想メモリ空間による分離もかなり積極的に使っているのかもしれません。

SIPを導入するためには、Javaのような実行時のポインタチェック、配列領域チェックなどが必要になります。この記事の結論では、これらのruntimeのコストは5%程度の効率低下に留まり、仮想メモリ分離をやめたことによるパフォーマンスゲインが38%もあるため、総じて安い、という事のようです。

SIPを使うとプログラムはリロケータブルにする必要があるので、元々共有ライブラリで実装されていたような物は差がないんでしょうが、プロセス分離に適用しちゃうとローダがリロケートするコストが馬鹿にならないような気はしました。

SIP間通信の仕組みとしては、強く型付けされたパイプを使っているようです。実データは同一メモリ空間内のExchange Heapと呼ばれるところに格納され、ゼロコピーでデータ交換しているように読めます。このあたりが効いて、low latency、high bandwidthなプロセス間通信が実現できる、という事のようです。また、通信には"contract"と呼ばれる仕組みが使われており、この辺も突っ込んで調べてみると面白そう。通信データを入出力としてステートマシンを記述して制御しているようなので、形式検証を使ってプロトコルチェックとかできるのかも。

最後の方では、kernelにGarbage Collectionを適用する事の是非について触れられています。kernel objectの多くはlifetimeが非常に長く、プロセスの開始から終了まで張り付いています。この種のobjectを大量にGCで管理したところで、メモリ回収のwalkingにかかるコストが大きくなるだけで、あまり旨みがないのでは、といった議論があるようです。

という事で、最近は懐古趣味ばかりでしたが、めずらしく先端研究についても調べてみました。