2012年12月22日土曜日

LispでOSを書く

(このエントリは、Lisp Advent Calendar 2012 の22日目である)

ELIS復活祭のとき、ELISのTCP/IPプロトコルスタックを書いたという方とお話する機会があった。ELISのプロトコルスタックはもちろんLispで書かれていた。その方がおっしゃるには、「C言語はよい。BSDからソースコードを持ってくればいいのだから。しかし、Lispで書かれたプロトコルスタックなどなかった。自分で書くしかなかった」ということだった。それにしても、LispでOSを書くというのは、いったいどんな感じなのだろう?

OS記述言語としてのLisp

UnixがCで書かれて以来、OSは、伝統的にCとその派生言語で書かれることになった。BSDやLinuxを含むUnix-likeなシステムはもちろんCで書かれている。Windows NTはC++を使っている。BeOSもC++で書いたし、MacOS XはObjective-Cを使っているのかもしれない。もしかすると、IBMのメインフレームなどでは事情が異なるのかもしれない。

Cとその仲間たちは、いわゆる高級言語の中でも抽象化のスペクトルのだいぶ下の方に位置している。つまり、ビットを操作するような処理が得意なのだ。だから、デバイスのレジスタを直接叩くような処理はCの得意とするところだ。

OSを構成するサブシステムの中でも、プロトコルスタックやファイルシステムは、デバイスを叩くというよりは、ある種のロジックを実装するものだ。80年代から90年代にかけて研究されたマイクロカーネルでは、これらのサブシステムはユーザプロセスとして実現されていた。

ソフトウェア工学の言葉を使うなら、OSのコア(マイクロカーネル)はデバイスへアクセスする「メカニズム」を提供する。上位のサブシステムは、そのデバイスをどのように使うか(例えば、ファイルシステムをどう構成するか)という「ポリシー」を実装する。

複雑なロジックを実装するためには、できるだけ抽象化のレベルの高い言語を使うべきだ。そして、もっとも抽象化のレベルの高い言語(のひとつ)はLispである。したがって、OSのサブシステムも、ある部分はELISのようにLispで書いてもいいはずだ。

FUSE + libfuse + Gauche + c-wrapper

LispでOSのサブシステムを書くというのがどんな感じなのか、試してみる方法をご紹介したい。私はCommon LispよりもSchemeの方が慣れているので、Gaucheを使うことにしよう。

1から新しいOSを設計するのは、楽しいかもしれないが時間もかかる。Linuxには、FUSE(Filesystem in Userspace)という、ファイルシステムをユーザ空間で実装するための仕組みがある。この仕組みを使って、Gaucheでファイルシステムを書いてみたい。

FUSEにつて簡単に説明しよう。Linuxカーネルは複数のファイルシステムを持っている。ext3, ext4, btrfsなどなどだ。それぞれのファイルシステムの開発者のために、カーネルとファイルシステムとの間に標準的なインタフェースが決まっている。このインタフェースをユーザ空間からアクセスできるようにする仕組みがFUSEだ。

最近のLinuxカーネルなら、FUSEは標準で組み込まれている。/dev/fuseがカーネルへのインタフェースだ。基本的には、普通のファイルアクセスのシステムコールを使って/dev/fuseを操作すればよいのだが、これをもう少し簡単に行うためのライブラリとして、libfuseがある。

libfuseはCのライブラリだ。libfuseをGaucheで使うにはCへのバインディングを書けばよいのだが、もっと簡単な方法は…そう、魔法のc-wrapperである。

hellofs (The Hello Filesystem)

ストレージを操作する本物のファイルシステムではなく(これは大仕事だ)、偽物のファイルシステム(Pseudo Filesystem)を実装してみる。これは、/procや/sysの一種と考えてよい。このファイルシステムは、FUSEのサンプルプログラムをほぼそのままSchemeで書きなおしたものだ(若干の手抜きをしたので、あまりいい例ではないかもしれない)。
#!/usr/bin/env gosh
# hellofs.scm (The Hello Filesystem)

(use gauche.uvector)
(use c-wrapper)

(c-load "fuse.h"
        :cppflags "-DFUSE_USE_VERSION=26"
        :cppflags-cmd "pkg-config --cflags fuse"
        :import '(fuse_operations
                  fuse_main_compat2
                  fuse_main
                  NULL)
        )
(c-load "stdio.h")
(c-load "string.h")
(c-load "errno.h")
(c-load "fcntl.h")
(c-load-library "libfuse")

(define hello-path "/hello")
(define hello-str "Hello world!\n")

(define (hello-getattr path stbuf)
  (memset stbuf 0 (c-sizeof (c-struct 'stat)))
  (cond ((string=? (cast  path) "/")
         (set! (ref stbuf 'st_mode) (logior S_IFDIR #o755))
         (set! (ref stbuf 'st_nlink) 2)
         0)
        ((string=? (cast  path) hello-path)
         (set! (ref stbuf 'st_mode) (logior S_IFREG #o444))
         (set! (ref stbuf 'st_nlink) 1)
         (set! (ref stbuf 'st_size) (string-length hello-str))
         0)
        (else (- ENOENT))))

(define (hello-readdir path buf filler offset fi)
  (if (not (string=? (cast  path) "/"))
      (- ENOENT)
      (begin (filler buf "." NULL 0)
             (filler buf ".." NULL 0)
             (filler buf ((#/^\/(.*)$/ hello-path) 1) NULL 0)
             0)))
      
(define (hello-open path fi)
  (if (not (string=? (cast  path) hello-path))
      (- ENOENT)
      (if (not (= (logand (ref fi 'flags) 3) O_RDONLY))
          (- EACCESS)
          0)))

(define (hello-read path buf size offset fi)
  (memcpy buf hello-str (string-length hello-str))
  (string-length hello-str))

(define hello-operators (make (c-struct 'fuse_operations)))

(set! (ref hello-operators 'getattr) hello-getattr)
(set! (ref hello-operators 'readdir) hello-readdir)
(set! (ref hello-operators 'open) hello-open)
(set! (ref hello-operators 'read) hello-read)

(define (main args)
  (fuse_main (length args)
             args
             (ptr hello-operators)
             NULL
             ))
マウントすると、マウントポイントにhelloというファイルが現れる。このファイルにはお馴染みの文字列が格納されている。
# mkdir /tmp/hello
# ./hellofs.scm /tmp/hello -d -s
...
# ls /tmp/hello
hello
# cat /tmp/hello/hello
Hello world!
マウントするときに、シングルスレッドモード(-sオプション)を指定することに注意して欲しい。libfuseは、その中で新たなスレッドを生成する。このスレッドはGaucheのスレッドではないので、この中からSchemeの関数をコールバックすることはできない。

FUSEを使ってストレージを操作するようなファイルシステムを作りたいのなら、デバイスノードを読み書きすればよい。また、ユーザ空間でできることは何でもできる。例えば、EvernoteやGoogle Driveにアクセスするようなファイルシステムを作ることもできるはずだ。

* * * 

OSのカーネルはますます大きく複雑になっている。Unixの第6版のソースコードは、印刷したものをブリーフケースで楽に持ち歩くことができるほど小さかった。今日のLinuxのソースコードを印刷して持ち歩くことは、不可能ではないが紙の無駄である。

 Unix第6版の時代からプログラミング言語の世界は大きく進歩した(もちろんLispはUnix第6版の時代から存在したのだが)。ところが、今日のOS開発者は、これら進歩的プログラミング言語の恩恵に与っていない。 

そろそろ、OS開発にも、次の世代のプログラミング言語を使ってもよいのではないかと思う。ELISは商業的には成功しなかった。しかし、ELISの開発過程で多くの知識が蓄積されたはずだ。(非常に失礼な言い方だが)ELISの開発者がまだ生きている今こそ、そのチャンスである(失礼しました)。

2012年12月15日土曜日

豊かな社会

私の母校は、工学部のみの小さな単科大学だ。工学部のみの大学であっても、いわゆる一般教養の授業がある。そのための常勤の教員もいる。特に人文社会系の講義のことを、私たちは単に「社会系」と呼んでいた。

私たちにとって、「社会系」の授業は悩みの種だった。これらの単位が、進級のための条件になっていたからだ。私たちは、エンジニアリングを学ぶために大学へ入った。そのために授業料も払った。確かに西洋思想史は興味深いかもしれないが、エンジニアリングとの接点を見出すことはできなかった。

大人になってから、「あの時もっと勉強しておけばよかった」と思わない人はいない。私もその例に漏れない。30歳を過ぎて思うには、もっと真面目に「社会系」の勉強をしておけばよかったのである。

実は、エンジニアリングと「社会系」は密接に関係していた。なぜなら、エンジニアリングとは、社会を豊かにする方法だからだ。学生時代の私は、エンジニアリングの方法論にばかり捕らわれ、その目的が見えていなかった。

19世紀の経済学者は未来を悲観した。保守主義者もマルクス主義者も、産業革命の行き着く先はユートピアではないという点では意見が一致していた。しかるに、二つの世界大戦を挟み、ヨーロッパ、アメリカ、日本を含む国々には、豊かな社会が誕生した。これらの国々の共通点は、エンジニアがたくさん住んでいるということだ。

失われた10年だか20年だか知らないが、日本企業が不調である。パナソニックが赤字という。シャープも赤字という。任天堂でさえ赤字という。日本の製造業は軒並み「オワコン」と言われる。どうしてしまったか?

日本の製造業も、学生時代の私と同様、方法論にばかり捕らわれ、社会を豊かにするという当たり前の目的が見えなくなっているように思う。私も、ついこの間まで日本の製造業に身をおいていたのでよくわかる。もっとも、彼らが捕らわれている方法論は、経営学のそれであるようだ。

何をもって社会の豊かさとするかは難しい。今年のはじめに、ロボット掃除機のルンバを買った。まるでSFの世界にいるようだった。ハインラインの『夏への扉』に出てくる家事ロボットのようだった。私の生活は豊かになった。

今年ももう終わりだ。毎年、その年のテーマを設定することにしている。来年のテーマは「社会系」にしようと思っている。今年のうちに、古本屋行きを免れた教科書を発掘しなければならない。

2012年12月13日木曜日

『オペレーティングシステム 設計と実装 第3版』を読んだ

1953年、ワトソンとクリックによりDNAの二重らせん構造が発見されたとき、生命には神がかり的なものは何もないことが明らかとなった。以来、生命をめぐる神学上の諸々の問題は、科学とエンジニアリングの問題となった。本書を読めば、読者は、オペレーティングシステムのカーネルについて同じ発見をすることになる。

本書は、私の家の積読本コーナーにもう長いこと置かれていた。本書の原書が出版されたのが2005年。本書は、その翻訳として2007年に出版された。翻訳が出版されてすぐに手に入れたのだが、ずっと読めずにいた。何度か読もうと挑戦したものの、途中で挫折してしまっていた。読書会にも参加したが、途中で脱落してしまった。

今回、何度目かの挑戦で、ようやく読み終えることができた。実は、この本を読むのには、少々コツがあったのだ。本書は、1000ページを超える大著である上、本の後ろ半分がソースコードという、かなり特殊な本である。

本書では、カーネル、デバイスドライバ、メモリ管理、ファイルシステムのそれぞれのオペレーティングシステムのコンポーネントについて、それぞれひとつの章が割り当てられている。それぞれの章は、以下の順番で構成されている:
  1. オペレーティングシステム理論
  2. MINIXによる実装の概要
  3. MINIXのソースコード解説
  4. ソースコード
ただし、ソースコードは、すべてまとめて本の後ろ半分に付録となっている。1と2は普通に(つまりシーケンシャルに)読むことができる。問題は、3と4を如何に読むかである。

今まで私がどうやって読もうとしていたかというと、3と4を逐一対応付けながら読もうとしていた。つまり、ソースコードをちょっと読んで、該当する解説を読み、そしてまたソースコードに戻るという具合だ。

この読み方は、非常にしんどい。本文とソースコードとを、頻繁に行ったり来たりしなければならないからだ。すなわち、コンテキストスイッチのオーバーヘッドが大きい。

コツは、ソースコードを先に読むことだ。解説を読まずに、まず、ソースコードを読めるところまで読む。多少わからないところがあっても、本文で解説されていることを期待して、どんどん読み進む。ソースコードをある程度まとまった量(私には1ファイル分くらいが丁度よかった)読んだら、解説に目を通す。すると、自分の理解が正しかったり、あるいは間違っていたことがわかる。

本書は、Linux誕生のきっかけとなった事で有名だ。しかし、オペレーティングシステムの教科書としても非常によい本である。本書の、オペレーティングシステムのソースコードを読むことで学ぶというアプローチは、オペレーティングシステムの真の姿を明らかにする。

著者のTanenbaumは述べている:
実際のOSの真の姿は、知性的な興奮に満ちたものとは程遠く、マイナーな雑用を行うコードの集まりである。しかし、このようなコードこそシステムの可用性を向上するためには非常に重要なのである。(p.637)
また、その少しあとで、こうも述べている:
優れたシステムと平凡なシステムの違いは、スケジューリングアルゴリズムのすばらしさではなく、細部まで正確に仕上げる配慮にあるのである。(p.637)
私自身の学生時代を思い返してみると、オペレーティングシステムの授業では、スケジューリングやページングのアルゴリズムばかりが印象に残っている。そして、オペレーティングシステムとは、普通のプログラムとはどこか異なる、摩訶不思議な、何か神がかったものという印象を持ってしまっていた。

ワトソンとクリック以来、生命は単なる有機化合物の塊となった。本書が明らかにしたように、オペレーティングシステムも、単なるCプログラムの塊に過ぎないのだ。