Lions' Commentary (9) - 読書会#1 -

なんと、Lions' Commentary on UNIX 読書会が開かれる、という事で参加してきました。

しばらく独りで読み進めていましたが、まさか読書会に巡り会えるとは！

って、改めて読み返してみると、日記のエントリに1年近いブランクがありますね。

やばいやばい・・・時間が経つのが早過ぎる。

読書会ってのははじめてだったんですが、この会では1章ずつ読み進めます。

まずは時間が与えられて個々に内容を理解。その後、みんなで内容について議論する、と。

初回だったので進め方を決めて、さわりを・・・って感じでしたが、次回からは

月1回のペースで2章ずつ進める事になりました。途中参加もOKだと思うので

興味のある方がいたらぜひ。

1章〜4章は飛ばして実際の内容に入る5章からやりました。

pre K&RなC言語がわけわからんので、やっぱり3章も見とけば良かった・・・

みたいな話もありますが、まぁ必要になったら戻るという感じで。

5章はメモリ管理とpanic用の簡易版printfのところです。

mallocとかprintfとかいう名前だけど、libcの同名関数とは別物なので注意。

内容自体は簡単ですが、癖のある当時の文法が一番の悩みどころでした。

・型について

intとポインタはともに16bit。unsignedという考え方は存在しない。

　　unsignedが必要な場合はポインタで代用する！！！

　　このためstructのm_sizeの型がchar *になっている。

　　ちなみにv7ではm_sizeはsigned shortだったりするけど。。。

・キャストが存在しない

　　キャストがないため「*((int *)アドレス直値) = 書き込み値」みたいに書けない。

　　そのかわり「->」を使うと型に関係なく構造体だと思ってメンバを探しにいく仕様で、

　　構造体の名前空間も単一。これを利用して例えばintのメンバintegを持つ構造体を定義し、

　　「アドレス直値->integ」と書く事で「*((int *)アドレス直値)」と等価になる。

　　現代人からすると超キモイ仕様。

・大域変数にextern宣言をしない

　　これは今でも通用するみたいなので、きちんとC言語の仕様をあたればそういう物かも。

　　大域変数はあるソース（.c）に実体を置き、他のソースからはヘッダ（.h）にextern宣言

　　された物をincludeして使う、というのが今時の描き方。

[foo.c]

　int global_variable;

　...

[foo,h]

　extern int global_variable;

　...

[bar.c]

　#include "foo.h"

　void bar (void) {

　　global_variable = 1;

　　...

　}

　　なのだが、実はexternは省略しても良い。リンク時に型や初期値の不整合がなければ

　　1つにまとめてくれる。実際、coremapとswapmapはsystem.hで宣言されており、

　　extern修飾もなければソース側での実体定義も存在しない。

・ldiv/lremはなぜアセンブラ？

　　当時のC言語は乗除算は使えなかった？　とか効率の良いコードが吐けなかった？

　　とか憶測が飛び交ったけど、結局は妥当な理由が見当たらない。

　　6th Cでのサポートはoracchaさんが試して通る事を確認しているし、吐かれるコードも

　　悪くはない（関数にしなければinlineで展開されるのでprolog/epilogも不要なはず）。

　　単純に前の版までアセンブラで書いてあったのでそのまま流用？とも思える。

　　あるいはKernel書いてる頃にはコンパイラがサポートしておらず、その後ユーザランドを

　　作ってるうちに面倒になってコンパイラサポートが入った、とか。

　　v7ではアセンブラは廃止されてCの演算子で書かれてたりするので、この線が濃厚か。

　　ちなみに、printnの最後はv6では「putchar(lrem(n, b) + '0');」という全うな書き方だが、

　　v7では「putchar("0123456789ABCDEF"[(int)(n%b)]);」という微妙な書き方に。。。

　　どう考えても遅いしメモリも食う書き方なので、こう書けるようになったのが嬉しくて

　　つい書いてしまったコードに違いない。

・改行後のDEL

　　改行がCRとLFにわかれているのと同様、歴史的な配慮？

　　consoleがプリンタだった場合、描画位置を左に戻して、紙を送って・・・

　　といった時間がかかるので、少し時間稼ぎ。

　　プリンタがreadyを返さなければXSTのbusy loopで待つ気もするけど。

・8進数

　　DECはPDP1の頃に8進数を使う文化が。。。

　　詳細はこの辺とか。

・可変長引数

　　stdargみたいな書き方は当然確立されていない。

　　もちろん、やってる事はva_startとかva_argの中身と一緒なんだけど、

　　実装を隠蔽せずに生でスタックを指すアドレスをずらして使ってる。

　　なので、無理矢理ダミーの引数を並べて書いてあるけど、実は意味がない。

　　引数を無駄に並べるのはv7で廃止されてるけど、実装はそのまま。

いくつか参考サイトを紹介します。

1. 2238クラブ または 私は如何にして心配するのを止めてUNIXカーネルを愛するようになったか ... 貴重な日本語情報サイト
2. Commentary on the Sixth Edition UNIX Operating System ... PDF版Commentaryあり
3. Dennis Ritchie Home Page ... 6th Edition UNIXのC言語リファレンスマニュアルあり
4. Operating System Engineering / xv6 ... x86/ANSI版
5. xv6詳説 ... xv6のソースをひらメソッドで読む
6. Plan9日記 2010-11-01 ... 読書会参加者のレポート
7. やる気のないはてだ 2010-10-31 ... 同じく参加者のレポート
8. PDP1 emulator on flash ... おまけ

近況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用は面倒な手順が色々と書かれてるんだけど、裏技的な方法として、
エンバイロメントのウィンドウを開き、レイヤーとしてテンプレートファイルを開く、
とかやると便利です。
テンプレートから設定をコピペしたり、作業をテンプレートから開始したり、
とかいう煩わしさ、制約から解放されます。

デーモン君のソース探検

中古で買った読み物シリーズ。

ずっとカーネルの手引書だと勘違いしてたんだけど、実はユーザーランドのハックの話。難易度的には低いので「Cの基本は理解していて、読み書きは普通にできます」くらいの人でも大丈夫。UNIXの伝統的なユーザーランドプログラムやライブラリなどを題材に、ソースの探り方、UNIXのお作法、などを指南。

さっと一読したけど、自分にとっては探検12 scriptで出てきたptty周りのお話、探検16 malloc()で出てきたPHK mallocのお話あたりが勉強になった。というか、もう一度読まないと、理解しきれていない。

パパ：え？　最近は中学校でもmmap()を習うのか？

とか、そんな親子の会話。私もしてみたいわー。

UNIX原典(1)

ベル研メンバーによる開発秘話本って事で、読み物として買ってみました。オリジナルはBell System Technical Journal 1984年8月号第2部UNIX特集号らしい。

技術書というよりは歴史書として買ったつもりだったんだけど、結構面白い。ライオン本だと「どう実装しているのか」は理解できても、「どうしてそう実装したのか」までは理解しきれない点も多々ありますが、この本読んでると、バグの話なんかも出てきて、意外なところで実装の意図が読み取れるかも？まだ読み始めたところなんで最初だけかもしれませんが。とりあえず面白いなぁ、という話があったので、それについて書いておきます。

file descriptorの実体については"Lions' Commentary (7) - closeとunlink -"で書いたとおりで、プロセスに直接ぶら下がっているのは実体ではなく参照です。プロセス内でユニークな番号が振られているので、プロセス固有のリソースのような気がするわけですが、実はシステム固有のリソースとして実装されている。forkの話もあるので、なんとなく「そうすべき」というのは直感としてあるのですが、いまいち必然性までは理解できていませんでした。

初期のUNIX@PDP-7ではShellがCP/MのCCPに近い実装になっており、ユーザ・プログラムではなくOSの一部として動いていました。その後、forkとexecが実装され、shellがユーザ・プログラムとして分離。今風のプロセス制御も導入されて、バックグラウンド実行なんかもできるようになりました。この頃はfile descriptorの実体がプロセスにあり、以下のようなコマンド（今風に書きなおしています）が正しく動作しなかったそうです。

$ (echo foo; echo bar) > log

期待される結果は

foo
bar

ですが、実際には

bar

になってしまう。ははぁ、確かにforkとexecの挙動を考えると、file descriptorがプロセスにぶら下がっていると、そういう事になりますね。このバグに気づき、file descriptorの実体はプロセスの外に追い出された、との事です。なるほど。
また、当初はchdirも外部コマンドとして実装されていたそうです。プロセス制御がなかった頃はカレントディレクトリはttyに括りつけで1つで良かったわけで、chdirはこの括りつけのカレントディレクトリを変更して親のShellに戻っていました。ところがプロセス制御の導入によりカレントディレクトリはプロセスごとに個別に持たせる必要が生じ、その結果として外部プロセスとしてのchdirを実装できなくなりました。最近のUNIXから入ってると、むしろ初歩的なトラブルって感じがしちゃいますが、当時はUNIXの生みの親たちですら理解に苦しんだバグのようです。コロンブスの卵的なところがあるのかな。

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にかかるコストが大きくなるだけで、あまり旨みがないのでは、といった議論があるようです。

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

オリゲー・フェスタ68

通称オリフェスに参加してきました。
自分のサークル名義じゃないけど、久々のイベント参加。

イモプロ名義で以下の物を展示してました。

• MegaZ-80K（最初の写真では画面左端より外側ｗ）

AVRをふんだんに使って再現したMZ-80K互換機。MEGA644でZ80エミュレーション。UARTベースで共有バスを張って、その上でI/O通してました。今回は足がいっぱいあったので、SRAMとはアドレス15bit、データ8bitを外部ラッチ無しで直に繋いでます。配線は圧倒的に楽ができた（笑。

画像表示はMEGA328が専任。ひたすらUARTモジュールを駆使してNTSC信号を作りまくるお仕事。I/Oからのアクセスにすぐに応答する余裕がないため、間にFIFOとしてのTINY2313がいます。
I/OバスとしてはシリアルでTINY2313がデータを掴み、HSYNCを待ってパラレルでMEGA328に流し込む感じです。

写真はMac上のGtkで書いてたプロトタイプに、シリアルで画面表示モジュールにデータを流し込むコードを追加し、エミュレーションで書いた画面と実際のビデオ出力を比較しているところ。











あとはサウンドもTINY2313が担当。こっちは割り込みでレジスタをパタパタさせて鳴らしております。

で、最後はなぜかファミコンコントローラ。色々とツッコミもありましたが（笑。キーボードどうしようかな、PS/2にしようかな、USBにしようかな・・・と考えていたらPS/2の端子が部品箱にない事に気づきました。USBならいっぱいあるけど、ホストは作ったことはないし・・・。という事で、手っ取り早く済ませよう、とファミコンを投入。やっぱりTINY2313を使っていて、キーボードに対するI/Oアクセスが来たらコントローラのステータスを読み出し、適当にスキャンコードにマップして応答を返しています。

• CP/Mega88（左端、iBook）

再びCP/Mega88。こっちもインベーダー動かしたりして展示してました。
ライセンスはどうなってるの？って人もいましたが、今は開放されてます。

• USB-PSG/SID（中央、MacBook）

USB接続のPSG音源とCommodore64のSID音源。Linux用のドライバしか書いてないので、デモはUbuntu上で行いました。fMSXのPSGアクセス部に手を入れてドライバのI/Oを叩くようにしています。Ys-IIのサウンドモードを動かしていました。
同じような事をやってます、って話をしてくれた人が何人かいましたが、Windowsでやってる人はドライバ部分で苦労してるみたいです。Linuxはその辺がお手軽だったので、独自クラスで適当なbulk転送のプロトコル決めて、ちゃちゃっと処理しちゃってます。
/sys/bus/usb/drivers/usb_psg/ 以下にデバイスファイルが出来て、そこ経由でレジスタ読み書きしたり、レジスタダンプ表示させたり。
USB部分はPIC18F2550ですね。今回唯一のPIC成分。PICだとUSBフレームワークがついててファーム開発もらくらく・・・というわけではなく、実は自分、商用コンパイラ使うのが許せなかったので、sdcc向けにスクラッチでUSBのファームを書きました。当時は自前でUSB周りを叩いたファームって見かけなかったけど、今だとどうなんだろう。シリアルからデバッグメッセージ吐きながら開発してましたが、うかつにメッセージ吐くとUSBのプロトコル側でタイムアウトが発生してしまうので、結構大変だった記憶があります。

Kerne/VM探検隊

Kernel/VM探検隊#4に参加してきました。
今回も色々と刺激的なお話が聞けました。
技術的にも、年齢層的にも、けっこう幅広いのが良いです。

yojiroさんのUSBデバイス解析の話は面白かった。
「俺の電線に流れる電気信号を観測して何が悪い」って、なるほど。
電子工作のデバッグでプロトコルアナライザ使ったら敗北感がありますが、
ソフト開発では漢のツールですね。

kobaさんのqemu+chrootの話もgood。
クロス環境作成にはいつも苦労するので。
こういう発想はなかったな。。。
linuxの/proc/sys/fs/binfmt_miscも今回はじめて知った。
そういえば、UNIXの「#!」の習慣はどこから始まったんだろう。
Ancient UNIXではこの習慣はなかった。
実行ファイルでなければシェルがそのまま実行してますよね。

ucqさんはバイナリエディタでプログラミング。
Plan 9を例にしてたけど、やっぱり一番簡単なのはX680x0の.r形式だな。
ヘッダ一切なしで、relocatableな実行列の塊。
自分は開発環境が入ってなかった部室のマシンで、しかたなく
TYPEコマンドでリセットコマンドを作った記憶がある。。。

shudoさん参加してたのか。
しかも発表側。
末尾再帰で最適化かかってるんじゃない？的なコメントもあったけど、
その時はスタックは呼び出し元と整合するように補正してからジャンプ
ってなるはずだし、やはり元作者のケアレスミスでは。

oracchaさんの発表でsocketはshutdownかけると相手側のreadが0で返り、
それをEOFとして処理するアプリが多いという事を知った。
signalが来た時もsystem call中断してhandlerに処理を移すけど、
あの時は-1か。確かにman 2 readに書いてある。
BeOSのsshがEOF検出できずに固まる事があったけど、あれはshutdownが
きちんと動いていなかったからなのだな。。。と今更気づいた。


そうそう、今朝、目覚めてふと疑問に思いました。
ファイルシステムのジャーナルってどの層でやってるんだろう。
普通UNIX系のシステムだと、デバイスの上にブロックデバイス
ドライバがあって、その上にバッファキャッシュが載っていて、
さらにその上にファイルシステムが載ってるはず。
トランザクションって意味ではファイルシステムの最下層で
ジャーナル録りたい気がするけど、その下のバッファキャッシュが
LRUで動いているので、それでは不意の終了に耐えられない。
かといってディスク直上でジャーナル録ってたら、
◯△fsのジャーナル機能が云々〜って話にはならないはずだし。