auto-apt 〜 その妄想と実装、およびさらなる妄想 〜 $Id: ukai.txt,v 1.1 2000/11/19 16:16:51 ukai Exp $ 前回の「でびるまんのための えるだっぷ はうつー」は思わず Linux Conference 2000/Fall のチュートリアルに続いてしまった(?)ので 今回は別の話でいこうと思う。名付けて auto-apt 〜その妄想と実装、およびさらなる妄想〜 である。 ■auto-apt その妄想 そもそものはじまりはいつだったか定かではないが、確か某IRCチャネルで 「apt-getは便利だねー」からはじまるたわいもない会話からでたアイディア だったと思う。その時はそのような妄想をするだけで「exec(2)をフックすれば できるよなー」と思いつつ、まともな実装はおこなわれなかった。 ちなみに試しにzsh の shell function で実装してみたことはある。 記憶によればzshで、command not found になった時に勝手にapt-get install を読んでinstallし、コマンドをやりなおすような function を作ったはずである。 ただし、試しに作っただけなので not found なコマンドからどのパッケージを インストールするか までは作っていなかった。command not found の時にある 特定のパッケージを apt-get install していただけである。 これは簡単に実装できたわけであるが問題としては zsh でしか使えない という点があり、この実装は闇の彼方に消えてしまった。手元にも残ってはいない。 それからずいぶん時間がたったある日、『でぶあん不徹底入門2000夏号』の 原稿「Debianを64倍ほど使うための本」の以下の部分を見て再びハック魂に 火がついたりしたわけだ(笑) | 余談だが、aptにハマって堕落しきったアレゲなでびるまんの間では、たとえば、 | C のソースをコンパイルしようとして make を実行したら | | gcc: コマンドが見つかりません | | などという状態になったとに、おもむろに apt-get install gcc が自動的に | 実行され、そのまま何事もなかったかのように作業が続行できる | | オンデマンドapt | | が実装されたら…などと妄想している人もいるが | (以下略) この妄想は昔から言われていたことだ。そしてたまたまアイディアが思いついて しまっていた。これは実装しないわけにはいかないだろう(笑) 世の中勢いが重要である。 ■auto-apt その実装 その1 〜プロトタイピング〜 この頃は Netscape Navigator のバグをなんとか回避するために preload ライブラリでまずいコードをオーバーライトして修正するということを やっていた。当然この「オンデマンドapt」にもそれが応用できるという のに気がついたわけである。昔思っていたように「exec(2)をフック」してやれば いいのだ。擬似コードで書けばこんなかんじだろうか。 int execve(const char *filename, char *const argv[], char *const envp[]) { int e; again: e = 「本当のexecve」(filename, argv, envp) if (e < 0) { switch (errno) { case ENOENT: if (まだ apt-get installしてない) { 「apt-get install "filenameを提供しているパッケージ"」 goto again; } break; default: break; } } return e; } execve()は filename をコマンドバイナリ(shell scriptかもしれない)を 引数を argv, 環境を envp として実行する。もし filename が なかった 場合は errno == ENOENT を返してくるので、この時に、そのファイル名を 提供しているパッケージを apt-get install してもう一回 execve()を やりなおせばいいのである。基本的な考えばこれで問題ないはずだ。 このようなコードで作った *.so を LD_PRELOAD で preload してやればいい。 すると execve() というシンボルに関しては、この preload した execve()が 一番最初に表われることになるので、プログラムが読んでいる execve() は こちらを参照するようにld.soによりbindingされる。従ってプログラムで execve()をコールすると上のコードが実行されるようになっているのである。 ここで問題になるのは 本当のexecve をどうやってcallするか である。どういうことかというと既に「execve()」という関数は上で 説明した関数を差すようになっている。従って、ここで素直に execve()を 呼ぶと自分自身をそのまま呼ぶようになってしまって意味がない。 libc のソースからコードをそのままとってくるという方法もなきにしもあらずだが それはバグを埋みやすいし、libcのコードの一部をとりだすのはとにかく面倒である。 そこで、次のような方法をとった。これは実は libc.so を dlopen(3)して、 dlsym(3)で execve の関数へのポインタを得ればよいのである。 void *handle; int (__*execve)(); handle = dlopen("/lib/libc.so", RTLD_LAZY); __execve = dlsym(handle, "execve"); e = __execve(filename, argv, envp); これでいける。こうすれば execve()はフックする方の関数。__execve()は libc.so にある本当のexecve() をさすことになる。 「まだ apt-get installしてない」は適当にフラグ変数でやればいい。 次の難問(というか真の難問)は 「apt-get install "filenameを提供しているパッケージ"」 である。まず "filenameを提供しているパッケージ" をどうやって得ればいいのか。 ここでコードのことは忘れて、普段ならどうやって探しているか考えてみると Contents-*.gz をとってきて zgrep する である。ではそれをコードにしてみればよいのだ。毎回 Contents-*.gz を とってくるのは無駄スギ遅スギなので、apt-get 同様 update する時に local cache にとってきてそれを参照するようにしておけばいいだろう。 それができれば、後は local のファイルを検索するコードを書けばいいだけである。 この時点でとりあえずアイディアが正しいかどうかは実際に動かして試してみる ことができる。この時点で全然動かないようなら、そのアイディアはそもそも駄目か どこか再考の余地があるはずだ。とりあえず速攻でコーディング、動かしてみる。 apt-get installの実行に関しては root 権限が必要とされるのだが、これは sudo を使うことでクリアしてしまう。で、これでとりあえずできたのだが 滅茶苦茶遅ぇよ… 遅すぎ という結論になってしまった。もちろん普段はexecve()のフックでそれほど 遅くはならないのだが、Contents の検索をしにいった時点で死ぬほど遅くなって しまう。これは高速化しないといけない。 ■auto-apt その実装 その2〜速くしましょう〜 やはり plain text を単純に検索するだけでは遅い。Contents に含まれている filenameの数を n とすると最悪 O(n) なのだ。これは遅い。やはりなにか検索 しやすいようなデータ形式にしないと駄目なのだ。最初に試してみたのが libc の db ライブラリを使うということだった。これはあまりドキュメントとか がなくてよくわからなかったのだが、単純に filename をキー (最初の)パッケージ名をバリュー にした db を作ってみた。これで確かに検索はそこそこ速くなったのだが 今度は Contents->db への登録が死ぬほど遅い (30分とかそれくらいのオーダー) という現実がつきつけられる。これはまいった。これでは apt-get update なみに気楽に使えない。せめて数分のオーダにならないと困る。 しかも db が巨大すぎる。しかしながら実際に実行するに際しては速度が それほど問題にはならなくなった。とりあえず db が巨大すぎるのが問題なので ad-hoc に対処してみる。それは filename は共通の部分文字列が多いのでそれを数文字で表現する というアイディアである。これでかなりサイズが小さくなった。また ディレクトリによってはファイル名とパッケージ名に関連がある というのも考慮にいれて db を作るようにすると サイズはそれなりに 許せるものとなった。しかし遅いのはあいかわらずだ。 ■auto-apt その実装 〜exec 以外もチェック〜 ほとんどのプログラムでは、ファイル名でファイルをアクセスするのに、基本的には ある限られた library call/system call しか使わない。要はこれらの library call/system call をフックし、もし失敗したら apt-get してやりなおす ようにすればいいわけである。 そのような library call/system call は以下のようなものがある。 * exec系 * open系 * access系 * stat系 あとは open()での file handle を参照してファイルにアクセスすることになる。 creat(2)に関しては、「パッケージで提供しているファイルを必要とした時に インストールする」というコンセプトなので creat(2)でユーザが作成しようと しようとした場合のことは考慮しなくていいと考えて creat(2)はフックしていない。 ■auto-apt その実装 〜やっぱりdb遅いよ? 速くしないと!〜 dbにして 検索するのは速くなり、小細工することでサイズは小さくなった わけですが、db作成が遅いのはあいかわらず(20分くらい?)。やはりこれでは 誰も使ってくれないだろうということで高速化を目指す。もちろん高速に するだけでなく dbのサイズもそれなりに小さくする必要がある。 これに関しては hattasサメとの切磋琢磨があったわけだが、結局現在は 次のような感じになっている * mempool メモリプール pointerを含むデータをファイルに入出力できるように * strtab ストリングテーブル ハッシュテーブル 同じ文字列は同じメモリを共有している * pkgtab package名を strtab で表現したもの * pathnode path名のツリーを表す構造体 各ディレクトリ内は ファイル名の二分木 (left, right) ディレクトリ名の時は down で差すツリーがディレクトリ内部 同じファイルを複数のパッケージが提供している場合は dups によるリスト * pkgcdb2 パッケージコンテンツデータベース 2 基本的な API は次のようなもの - pkgcdb_load() - pkgcdb_save() - pkgcdb_get() - pkgcdb_put() - pkgcdb_del() - pkgcdb_traverse() strtabによる文字列のハッシュ化、pathnodeでのファイル名の二分木により db作成もかなりの高速化、省サイズ化ができた。やはり基本的アルゴリズムを いろいろと知っていないと損だなと身にしみた出来事であった。 ■auto-apt その実装 〜installerは別プログラムで〜 当初、auto-apt は apt-get isntall する時に auto-apt.so の中で直接 apt-get install を実行していた。しかしながらこの方法だと、複雑な ことをしようとすると面倒なことになる。また、tty じゃなくて X Window Systemな環境で使っている場合、やはりウィンドウをあけてそこでいろいろ 選択できる方がうれしいに違いないと思った。そこで apt-get install を直接実行するかわりに auto-apt-installer という外部サポートプログラムを 作成することにした。これは Perl/Gtk なんかを使って複数パッケージが 特定のファイルを提供している場合にGUIで選択できるようにしてみたのである。 ■auto-apt さらなる妄想 現状でもそれなりに使えるのだが、auto-apt に関してはさらなる妄想が 残っている。 * negative hint? auto-apt を使っていると場合によってはインストールしたくないものを 何度も何度も「インストールするか」と聞いてくることがある。 auto-apt-installer あたりで、「インストールしない」を「今はインストール しない」と「今後もインストールしない」あたりに分割してインストールしない リストを管理すべきだろう。 * auto-apt-installerの debconf化? なんか taru がやっているらしい? * readdir(3)をモゲる プログラムによっては ディレクトリの中身をリスティングしてから ファイルにアクセスしにいっているものがある。そういうプログラムが アクセスするファイルに関してはディレクトリエントリにそのような ファイルがないとそもそもアクセスにいかないので auto-apt でひっかける ことができない。これは readdir(3)などの DIR* をあつかう library call をフックすればできるはずだ(と妄想中) * unlink(2)をフック パッケージが提供しているファイルを削除しようとしたら パッケージ自体を 削除しようとしてみたり? * auto-menu, auto-emacsen このあたりもフックできれば オンデマンドインストーラとして完璧? さすがに auto-inetd はセキュリティ上よろしくないように思うが(笑) 今のところ readdir(3)あたりはがんばればなんとかできそうな予感なので これができたあたりで auto-apt 0.4 としたいところだ。さて、 今世紀中に実装できるのか?! というあたりで、つづいたり、つづかなかったり…