初期化されていないプロックのアドレスは、 bat 内でも 間接プロック内でも 0 である。初期化されていないプロッ クが実在しないことはユーザーからは見えない。オペレー ティング・システムは、初期化されていないプロックの読 取りがおこなわれると、すべてのバイトに 0 を返す。一般 的なファイルで初期化されていないセグメントをしばしば 含むような構造をもつものは、ハッシュファイルである。 ロ ファイルシステム・フォーマット UNIX のファイルシステムのレイアウトは、 4 つのセク ションからなる。各ファイルシステムの最初のプロック ( プ ロック番号は 0 から始まる ) は、プートプロックである。フ ァイルシステムがプート可能なものである場合、このプロ ックはオペレーティング・システムのプートストラッフ・ コードを含んでいる。しかし、プートできないファイルシ ステムのプートプロックも予約されている。ファイルシス テムの 2 番目のプロックは、スーパープロックである。 れは、ファイルシステムのすべての管理情報を含んでいる。 ファイルシステムの i ノードとみなしてもよい。スーパー プロックの後ろには、 i ノードリストが続く。 i ノードリス トは、そのファイルシステムの全 i ノードの固定長の配列 である。最初の i ノードは現在使用されておらす、 2 番目は そのファイルシステムのルートディレクトリである。ほか の i ノードはあらかしめ割り当てられていない。 i ノード番 号は、 0 ではなく 1 から始まる。これは、ディレクトリ・ 工ントリが削除されたことをマークするために、 i ノード 値 0 が使用されるからである。最後のセクションは、デー タブロックを含む。 ファイルシステム上の任意のファイルにアクセスするに は、ますスーパープロック内の管理情報が必要となる。ス ーパープロックのディスク上に格納されているとおりの構 造は、く sys/filsys. h 〉 (System V. 4.0 では、く sys/fs/s5fil- sys. h 〉に置き換えられている ) のなかで定義されている。 スーパープロックから得られるもっとも重要な値は、論 理プロックサイズである。これは、しはしばデバイスの物 理プロックサイズと異なっている。論理プロックサイズは、 マジックフィールドとタイプフィールドによって決まる。 マジックが特定のマジック番号と同し場合には、タイプが ファイルシステムのタイプの決定に使用される。次のマク 110 ロは、マジック番号と異なるファイルシステム・タイプの ためにく sys / filsys. h 〉内で定義されている。 FsMAGIC / * マジック番号 * / / * 512 ノヾイトプロック * / Fs lb / * 1024 ノヾイトプロック * / Fs2b / * 2048 ノヾイトプロック * / Fs4b UNIX MAGAZINE 1991.6 働く不正な値はなく、データブロックのフリーリストには ンされる。一方、データブロックのほうではマーカとして れると、これを再び満たすために i ノードリストがスキャ シュとして働くことである。このキャッシュが使い果たさ リーリストの唯一の目的は、高速アクセスのためのキャッ ことによって表される。スーパープロック内の i ノード・フ らない。フリー i ノードは、ファイルタイプを 0 に設定する ドとプロックが割り当てられるか把握していなけれはな ファイルの作成と削除の過程で、システムはどの i ノー るパックの名前 ( disk0 など ) である。 ムの名前 ( root 、 usr など ) とファイルシステムを含んでい ィールドと fpack フィールドは、それぞれファイルシステ の場合には、特殊な状態 FsBAD が使用される。 fname フ とが分かっている場合でもマウントすることができる。 ただしルート・ファイルシステムだけは、壊れているこ FsBADBLK である。 いてマウントされていないファイルシステムの場合は、 ウントされている場合には、 FsACTIVE になる。壊れて れていないことを意味する。完全なファイルシステムがマ FsOKAY はファイルシステムに損傷がなく、マウントさ 状態フィールドは、ファイルシステムの状態を表す。 スの正当性を検査するために使用できる。 フィールドは、 i ノード番号およびデータブロック・アドレ ク数は fsize に格納されている。 isize フィールドと fsize isize に格納されている。ファイルシステム内の合計プロッ i ノードリストの直後の最初のプロックのアドレスは、 と i ノードリストのあいだには隙間ができることになる。 ズと物理プロックサイズが異なる場合、スーパープロック 論理プロック 2 から始まる。この結果、論理プロックサイ 物理プロック 0 と 1 に格納されている。 i ノードリストは らなくてもアクセスできなくてはならないので、それぞれ プロックとスーパープロックは、論理プロックサイズを知 ナルの 512 バイト・プロックサイズに仮定される。プート マジックが FsMAGIC と等しくない場合には、オリジ

連載 / Li 眈 Language 図 3 有向グラフの例 図 2 構文解析木の例 n 1 n3 n 1 n2 n3 n2 n4 = set() nl します。一方、 1 要素リストは被演算子の本体を表現して = set() Ⅱ 2 Ⅱ 3 ・ = set() います。 insert ( Ⅱ 1 , れ 2 ) この例に含まれてはいませんが、単項演算子とその被演 insert ( Ⅱ 1 , Ⅱ 3 ) insert ( Ⅱ 2 , れ 3 ) 算子を 2 要素のリストで表現するルールを追加すると、 insert ( 2 , れ 2 ) の形式のリストで数値演算式を表現できることになります。 3 つのノード nl 、 n2 、 n3 のあいだの関係は、各ノード レコードで表現する構文解析木 に対応する集合とその要素で表現されていることに注目し さきほどの構文解析木は、リストではなくレコードを使 てください。 nl は要素として n2 と n3 をもっており、これ って表現するともっと分かりやすくなります。そこで、 により nl から n2 への参照と nl から n3 への参照が表現 node 型のレコードを導入してみることにしましよう。 されているというわけです。一方、 n2 は n3 と n2 自身を要 素としてもっています。集合が自分自身を要素としてもっ record node (value , left , right) ているのは少々奇妙ですが、この例の場合はノードの自己 = node("j't) 参照を表現しているのです。 = node("k") n5 = node("*", n4, n5) n3 ORAPERL ? = node("i") n2 = node(" + ", n2, n3) nl 「 lcon 入門 ( 3 ) 」 ( 1991 年 4 月号 ) でも述べたように 以前に OraCon, すなわち lcon に Oracle データベー 、 IC on 処理系は引数が不足の場合には自動的に値 & null を補い スへのインターフェイスを追加したものがあるらしいと書 ます。したがって、ノード n4 、 n5 、 n2 ではフィールド left きましたが、 USENET のニュースグループ comp. と right はそれぞれ & null となり、それをもって解析木の source. misc を久しぶりに調べてみたら、なんと perl に リーフ ( 末端 ) を表現しているというわけです。 Oracle インターフェイスを追加するためのソースコード が流れていました。名付けて "oraperl"o 作者はフランス 集合で表現する有向グラフ 人です。 OraCon といい今度の oraperl といい、皆、よく 有向グラフとは数学用語の 1 つで、てっとり早くいえは 似たアイデアをもっているものですね。 矢印つきの線で結はれた点の集合のことです。有向グラフ は、関連づけられたデータのあいだの依存 / 参照関係を図式 化する目的でよく用いられます。 たとえば、図 3 のような有向グラフを lcon のデータ構 造の 1 つである集合で表現するとどうなるでしようか ? 0 0 / / 0 0 107 UNIX MAGAZINE 1991.6

IJN Ⅸへの招待⑩ 納されています。前述のとおり、 i ノード番号とは個々の i ノードにつけられた一意な番号です。さて、 1 つのファイ ルには 1 つの i ノードが割り当てられることになっており、 その i ノードにはファイルの所有者、リンク数、時刻情報、 ファイルの内容がディスク上のどのプロックに書き込まれ ているかなどの情報が格納されています。、、リンク数クと は、その i ノードを参照しているファイルの数のことです。 たとえば、ファイル A を B にハードリンクすると、 A に割 り当てられていた i ノードのリンク数は 2 となります。 ファイルシステム内には、このようにファイルが格納さ れています。したがってコマンドなどの引数でファイルを 指定すると、カーネルはディレクトリ内のファイル名から そのファイルに割り当てられている i ノード番号を検出し、 i ノード内の情報からファイルの実体を捜しあてていくわ けです。 今度は、ファイルの作成や削除の際のカーネルの働きを 考えてみます。皆さんがファイルを作成するとき、ごく大 雑把にいうと次のような作業がカーネルによっておこな われます ( カーネル内では、実際にはもっと複雑な操作がお こなわれています ) 。 cl ) ファイルの名前をメモリ上に読み込まれたディレクト リに書き込む。 (2) 未使用の i ノードが、新しいファイル用の i ノードとし て割り当てられる。 i ノードにはファイルの所有者や時 刻などに関する情報が書き込まれるが、それは ( ディス ク上に直接ではなく ) メモリ上でおこなわれる。 c3 ) 割り当てられた i ノードの番号が、メモリ上のディレク トリに書き込まれる。 (4) (2) の i ノードがメモリ上からディスク上へ書き込ま (5) (4) のディレクトリがメモリ上からディスク上へ書き 込まれる。 一方、ファイルを削除すると次のような作業がおこなわ れます。 % grep fsck /etc/rc /etc/fsck -p 162 dl ) 削除するファイルの名前が登録されているディレクト リで、該当ファイルに対する i ノード番号を 0 に設定す る。 (2) i ノード中のリンク数を 1 つ減らす。リンク数が 0 にな れば、その i ノードを未使用の i ノードとする ( さらに、 ファイルが使用していたディスク上のプロックを解放す る ) 。 こで、 UNIX マシンの電源がふいに切られてしまった としましよう。そのとき、不幸にもファイルを作成してお り、カーネルは c4 ) の作業が終ったところだったとします。 すると、ディスク中では使用されていることになっている i ノードの番号は、 c5 ) の作業が終っていないので、ディス ク上のどのディレクトリ中にも含まれないことになってし まいます。したがって、ファイルは作成したのにディスク 中のどのディレクトリにもその名前は登録されていないわ けですから、実際にはそのファイルが扱えなくなってしま います。 一方、電源が切られたとき、ファイルを削除していたと しましよう。カーネルは (l) の作業を終えたところだった とすると、 i ノードは未使用になってません ( 使用中になっ たままです ) 。そこで、ディレクトリから参照されていない i ノードが、使用中となったままになります。また、たとえ 別のディレクトリからその i ノードが参照されていたとし ても、リンク数が減らされていない ( (2) が終っていない ) ので、 i ノード中のリンク数は実際の参照数より 1 つ大き いままになってしまいます。 皆さんも、、、 UNIX ワークステーションの電源はいきな り切ってはいけない〃と聞いたことがあるのではないでし ようか。その理由は、このあたりにあるのです。ふいに電 源を切ると、ディスク中の情報が誤ったものになってしま います。そこで UNIX では、万が一ふいに電源を切った場 合でもディスクの情報を正しく回復できるよう、 fsck とい うコマンドが提供されています。そして、立ち上け時のシ ェルスクリプト / etc / rc では、この fsck コマンドが実行さ れるようになっています。 >/dev/console 2 > & 1 UNIX MAGAZINE 1991.6

されるテープルであり、 i ノード自体のなかにファイル名はない。 つまり、ファイル名はほかの多くのシステムとは異なり、フ ァイルに不可欠な要素ではない。事実、ファイル名のまっ たくない一時ファイルを作成することさえ可能である。 ファイルのデータは、 i ノードの addr フィールドに格 納されているプロックアドレス・テーフ・ル (blockaddress table 、以下 bat と略す ) を介して位置づけられる。 bat の サイズとテープル内の個々のプロックアドレスは変化する が、たとえはプロックアドレス・サイズを 3 バイト、 bat の 長さは 13 プロックアドレス、プロックサイズは 1 , 024 バ イトとする ( addr フィールドのよけいな部分は埋められ、 i ノードの大きさがプロックサイズのなかに均等に分割さ れるようにする ) 。これは最大ファイルサイズが 13KB に すぎないことを示しているが、もちろんこれでは使い物に ならない。この制限を拡張する明快な方法が 2 つある。つ まり、プロックサイズもしくは bat 内のアドレスの数を大 きくすればよいのである。しかし、実装の条件として i ノー ドとプロックサイズが固定長であることが必要なので、ど ちらの方法をとっても許容できるファイルサイズに至る よりすっと前に現実的な限界に達してしまう。 このジレンマを解消するのは間接プロックである。 bat の最後の要素を間接プロックアドレスとして使用すること を考えてほしい。つまり、このアドレスのプロックはデー タではなく、より多くのプロックアドレスを含んでいるの である。プロックサイズが IKB でプロックアドレス・サイ ズが 3 バイトである場合、これによってファイル内でアド レス可能なプロックの範囲は、 12 十わ / 愿た / 況 d の・ s た、 すなわち 353 個の 1 KB プロックということになる。 この増加は大きな改善であり、このために必要な記憶領 域のコストはたったの 1 プロックである。間接プロックは bat の最後に位置しているので、 12KB 未満のファイルに はまったく無駄がない。 12KB 以降のデータをアクセスす る場合にも計算コストがかからない。これは、間接プロッ #include く fcntl . h> #include く unistd. h> int fd; UN Ⅸファイルの復元ー クがデータと同しように読めればよいからである。オーバ ーヘッドは、同しファイルに繰り返しアクセスする場合に ついては、オペレーティング・システムの内部バッファリ ングによって小さくなる。 しかし、 13 のプロックをすべて間接プロックにしたとこ ろで、妥当なファイルサイズの上限にはならない。そこで、 間接のレベルを追加する。二重間接プロックアドレスは、 単間接プロックアドレスを含むプロックを指し、これはさ らに直接プロックアドレスを含むプロックを指す。単間接 プロックアドレスを bat の 1 スロットに増やして ( 直接ア ドレスと同様に、そのアドレス範囲内のほうがアクセス効 率がよい ) 、最後のアドレスを二重間接にすることにより、 ファイルサイズの上限は 11 十わ s た / わ〃 dd た十 ( 況ん s た / 況イイた ) 2 すなわち 113.9MB となった。こ の変化は妥当なものであるが、それでも大満足というわけ にはいかない。そして三重間接プロックアドレスが追加さ れ、最大ファイルサイズは 10 十わ s た / わ / ん〃 d バた十 ( わた / ん〃靃 s た ) 2 十 ( 況なた / わ〃イバた ) 3 すなわ ち 37 .9GB となった。 i ノードのサイズを増やすことなく、ほとんど無限のフ ァイルサイズが実現できた。 IKB プロックの場合、 3 バイ トのプロックアドレスでは 224XIKB = 16GB までしかア ドレスできないので、いまや制限要素はプロックアドレ ス・サイズである。この構成は実際に最高の性能を引き出 すことが分かっているので、ほとんどの UNIX の実装で は、 bat のなかに 10 の直接、 1 つの単間接、 1 つの二重間 接、 1 つの三重間接を備えている。 i ノードファイル構造の興味深い特徴は、書き込まれな いプロックにはまったく記憶領域を割り当てる必要がない ことである。 lseek と write がファイルの終端を無視する ことを思い出せば、以 - ドのコード片が 3 プロック ( 1 つのデ ータブロックと 2 つの間接プロック ) しか使わすに IOMB のファイルを作成することが分かる。 fd = open("tenmegfile" , O-WRONLY ー 0 CREAT ー O-TRI-JNC , 0644 ) ; lseek(fd, (long) ( 10 * 1024 * 1024 ー 1 ) , SEE} く -Sff) ; (unsigned) 1 ) ; write ()d , close (fd) ; UNIX MAGAZINE 1991.6 109

UN Ⅸへの招待 # cd /usr/sys/conf # cp GENERIC SNOOPY # vi SNOOPY ←コンフィキュレーション・ファイルの編集 # mkdir /usr/sys/SNOOPY # /etc/config SNOOPY # cd /usr/sys/SNOOPY # make depend # make # mv /vmunix /vmunix. 01d cp vmunix /vmunix このあと、新たに作成したカーネルを立ち上げるため、 りますにれがシンポリックリンクが提供されるにいたっ ドがそれぞれのファイルシステムに存在していることにな ステム内で一意ですから、同し i ノード番号をもつ i ノー i ノード番号と呼びます。 i ノード番号は 1 つのファイルシ システム内で一意な番号がふられています。この番号を、 システムを作ったときにたくさん用意され、そのファイル 割り当てられることになっています。 i ノードは、ファイル よう。 UNIX では、 1 つのファイルには 1 つの i ノードが めの機能です。ここでは、その仕組みを簡単に説明しまし ル名を使って同しファイルにアクセスできるようにするた 前号でもすこし触れましたが、リンクとは異なるファイ クも可能です。 リのリンクも、異なるファイルシステムのファイルのリン もできません。一方シンポリックリンクでは、ディレクト 中のファイルをほかのファイルシステムにリンクすること トリのリンクはおこなえませんし、あるファイルシステム ァイルしかリンクできません。ハードリンクではディレク ードリンクでは、同しファイルシステム内の通常のフ 呼ぶ ) の 2 種類があります。 ードリンクとシンポリックリンク ( 、、ソフトリンク〃とも リンクについて説明します。リンクには、前号で紹介した リックリンクされています。ここでは、そのシンポリック さて、さきほど述べたように /sys は /usr/sys にシンポ シンポリックリンク ちんと読み、その記述にしたがって操作をおこなってくだ ネルを構築する場合には、提供されているマニュアルをき 個々にさまざまな改良を施しているようです。実際にカー 以上の操作については、 UNIX マシンの各メーカーが システムをリプートします。 158 た重要なポイントです ) 。 さて、ファイルを作ったディレクトリには、ファイル名 とそのファイルに割り当てられた i ノード番号のペアが登 録されています。 i ノードには、ファイルの種類、ファイル の保護モード、ファイルの所有者 / グルーフ。所有者、ファイ ルの時刻情報、ファイルの実体が格納されているディスク 上のプロックのアドレスなどの情報が収められています。 ューサーがあるファイル名を指定すると、カーネルはディ レクトリのなかからそのファイル名を検出し、ファイル名 とべアになっている i ノード番号をもとに、そのファイル に割り当てられた i ノードをアクセスします。 i ノードには ディスク上のプロックアドレスが入っていますから、その 情報をもとに実際のファイルの内容がアクセスされるわけ さて、 A というファイルを B というファイルにハー ンクしたとしましよう。 A には、 i ノード番号 10 の i ノー ドが割り当てられているとします。すると以下に示すよう に、 B が登録されたディレクトリには、 B という名前と A と同し i ノード番号の 10 番のペアが登録されます。 この結果、 A という名前でアクセスしても B という名前 でアクセスしても、いすれも i ノード番号 10 番の i ノード がアクセスされることになり、同しファイルの実体にいき つくことになるわけです。これが、ハードリンクです。ハ ードリンクで異なったファイルシステムのファイルをリン クできない理由は、こにあるのです。ファイルシステム には、それぞれ一意な i ノード番号をもつ i ノードが存在 していますが、ファイルシステムが異なれば、それは一意 なものとはいえなくなってしまいます。というのは、ファ イルシステム / usr にもファイルシステム / tmp にも 10 と いう番号の i ノードが存在しているからです。 10 B UNIX MAGAZINE 1991.6

UN Ⅸファイルの復元■ リスト 2 getdinode 関数 #include く error. h> #include く limits. 血> #include く fcntl. h> #include く tmistd. 五> #include く sys/types. h> #include く sys/ino. h> #include く sys/stat. h> #include く sys/statfs. h> " /dev/dsk" #def ine FSIEIDIR char * devtonam(dev—t dev) ; / * getdinode: ディスクの i ノードを取得する * / int getdinode (const char *path , struct dinode *d1P) int int fsfd = 0 ; / * ファイルシステムのデノヾイスファイル記述子 * / / * 読み取られた文字数 * / / * ファイルシステムのデハ・イスノくス名 * / fspath[PAn-I_MAX + 1 ] ; chal 、 / * 汎用 i ノード * / struct stat st ; / * 汎用スーノく一プロック * / struct statfs stfs ; / * ファイルシステムの論理プロックサイズの取得 * / if (statfs (path, &stfs , (int)sizeof (stfs) , の return ー 1 ; / * ファイルの i ノード番号とファイルシステムのデハ・イス id を取得 * / if ( stat (path , &st) return ー 1 ; / * ファイルシステムのプロック・スペシャルファイルをオープン * / sizeof(struct dinode) * (st. st-ino ー 1 ) ) , SEEK S€r) if (lseek(fsfd, (long) (stfs. f—bsize * 2 + / * i ノードのシーク * / return ー 1 ; if (fsfd = fsfd = open(fspath, 0 RDONLY) ; sprintf (fspath, "%s/%s" , FSDEVDIR, devtonam(st. st-dev)) ; / * ファイルシステムのプロック・スペシャルファイルをクロ return ー 1 ; if ( 皿 ! = sizeof(*dip)) { 皿 = read(fsfd, (char *)dip, (unsigned)sizeof(*dip) ) ; / * i ノードの読取り * / return ー 1 : close(fsfd) ; return 0 ; 常のオペレーティング・システム・サーピスではそのファ イルシステム上のファイルにアクセスできなくなる。ファ イルシステムのアンマウントは、ファイル復元のような日 常的な操作には実際的ではない。しかし、ディスク・オプ ティマイサなどには向いている。 ロ 削除されたファイルの復元 UNIX ファイルシステム上の削除されたファイルを復 元する方法は 2 つある。 1 つは、ちょうどオペレーティン グ・システムがファイルにアクセスするときと同様に、フ ァイルの bat と間接プロックをたどるものである。もう 1 つは、新しく解放されたプロックのアドレスを見つけるた UNIX MAGAZINE 1991.6 めにフリーリストをスキャンするものである。どちらのア プローチにも長所と矢可斤がある。 bat 方式の短所は、先行操作を必要とすることである。 ディレクトリ・エントリがいったんアンリンク (i ノード番 号フィールドを 0 にセット ) されると、ファイル名とファイ ル本体とのあいだにはもはやなんの関連もなくなる。つま り、ヾそこからここへ持ってこられない〃のである。削除さ れたファイルの位置を見つけるには、ディレクトリ・エン トリがアンリンクされる前に i ノード番号はどこかに保存 されている必要がある。大部分のシステムでは、 bat そのも のを保存しなけれはならない。というのは、解放時にすべ ての i ノードが初期化されてしまうからである。 フリーリスト方式の長所は、 bat が失われてしまったフ 113

fsck は、ディスクのファイルシステムの内容に矛盾がな いかを調査し、矛盾があれはそれを修復します。たとえば、 前述したおかしなリンク数 ( 実際の i ノード参照数よりも 大きいなど ) を検出し、それを直したりします。また、実際 に i ノードは使われているけれども、その i ノード番号が どのディレクトリにも登録されていないなどの問題点も検 出します。 lost 十 found の話に戻りましよう。 lost 十 found は、遺失 物取扱用ディレクトリとして fsck が使用します。 fsck はい実際に使われてはいるが番号がどのディレクトリにも 登録されていない〃 i ノードを検出すると、その i ノード番 号を lost 十 found ディレクトリに登録します。また、ファ イル名を lost 十 found に登録し、あとからユーザーがその ファイルをファイル名で扱えるようにします。しかしこの とき、実際にユーサーがファイルにつけた名前は見つけよ UN Ⅸへの招待⑩ 、ゝうがありません ( ファイル名の情報はディレクトリにしか 置かれないからです ) 。そこで、 fsck は i ノード番号を一部 に使用した仮の名前をファイル名としてつけ、それを lost 十 found ディレクトリに登録します。もし自分のファ イルが lost 十 found に登録されたら、ユーサーは mv コマ ンドを使ってそれを適切なディレクトリに適切な名前で移 動します。 lost 十 found ディレクトリの役割はお分かりいただけた でしようか ? ところで、ツリー構造のなかにはルートディ レクトリの下だけでなく、あちらこちらのディレクトリに lost 十 found ディレクトリが存在します。 lost 十 found デ ィレクトリは、 1 つのファイルシステムに 1 つ存在させて おくからです。たとえは次に示すように、、ルート〃とソ usr 〃 の 2 つのファイルシステムからツリー構造が構築されてい るとしましよう。 % 矼 FiIesystem /dev/sdOc /dev/sdOd kbytes 7655 71551 us ed 6131 59071 avail capacity Mounted on 89 % 758 92 % 5324 この場合は、 / にも /usr にも lost 十 found が存在します。 % ls -dl /lost + found drwxr—xr—x 2 root 8192 Jan 1 1970 /lost + found % ls -dl /usr/lost + found drwxr—xr—x 2 root 4096 J 田 1 1 1970 /usr/lost + found fsck は、ファイルシステムの検査をおこなうコマンドで す。つまり、ルートを起点にしたツリー構造本ではなく ファイルシステムごとに検査をおこないます。ですから fsck が利用する lost 十 found は、それぞれのファイルシス ()d /tmp; find . ! -name ! —name 10St 十 found ! という言当があったのを思い出してください。 fsck にとっ て、 lost 十 found は必須のディレクトリです。このため、あ るパーティションにファイルシステムを作成した段階で自 動的に lost 十 found ディレクトリが作成されるようにな っています。 さて、あるファイルシステムを作成し、それを / tmp にマ ウントして使っていたとします (/tmp に 1 つのファイル システムをマウントして使用するということはよくおこな UNIX MAGAZINE 1991.6 、ゝテムに 1 っすっ存在しているのです。 fsck は、 lost 十 found が存在しないとファイルが宙に浮い ないとそれを作成するように拡張されています ( 以前の けです。もっとも、現在の fsck は、 lost 十 found が存在し 用いたファイルやディレクトリの削除をおこなっているわ found も消えてしまいます。そこで、 / etc / rc では find を レクトリを ()m -rf などで ) 全部消してしまうと、 lost 十 われます ) 。すると、立ち上げ時に / tmp のファイルやディ ーれ e quotas -exec -r { } \ ; ) こで、立ち上げ時のシェルスクリプト / etc / rc のなか たままになってしまいました ) 。 163

単独のフリープロックがすべて記されていなければならな い。しかしスーパープロックは明らかに、ファイルシステ ム内のすべてのフリープロックのアドレスを保持できな い (NICFREE は通常 50 程度にすぎない ) 。フリーリスト に十分な容量を与えるには、リンクプロックと呼ばれるフ リー・データブロックにチェインされなければならない。 s ー free がいつばいのときにフリーになるプロックは、リン クプロックになる。 s ー free の内容は新しいリンクプロック の先頭に移され、 s-free を空にし、リンクプロックのアド レスが s ー free の最初の要素に置かれる。リンクプロック がない場合には、 s-freeC0] は 0 である。 フリーリストの代わりに、ビットマップをプロック割当 ての追跡に使用することもできる。この方法は、ファイル システムの一部 ( 通常は、 i ノードリストとデータブロック のあいだ ) をビットマップのために必要とする。記憶領域の オーバーヘッドは重要ではない ( 1 プロックにつき 1 ピッ トにすぎない ) 。しかし、プロックが割り当てられるときの ビットマップ・サーチにかかるオーバーヘッドは、あっさ り見過ごすわけにはいかない。問題は、フリープロック・ アドレスを i ノードの場合と同様にキャッシュすることに よって解決される。 ロ ファイルシステムへの直接アクセス デバイスは、 open 、 read 、 lseek などを用いて、通常の ファイルと同様にアクセスされる。ファイルシステムに直 接アクセスするには、デバイス・スペシャルファイル名が 必要である。共通デバイスの命名には厳格な規則が適用さ れる。 通常、ファイルシステムは固定されたディスク・パーテ イションに格納され、 c / の s んの形式のファイル名がえ られる ( / はコントローラ番号、ゾはコントローラ上のドラ イプ番号、んはドライプ上のパーティション番号 ) 。これら はすべて、 0 から始まる 1 桁の小文字の 16 進数である。コ ントローラ 0 のドライプ 0 である c0d はなくなり、 0s 々の 形式の名前が残っている。パーティション番号 0 は物理デ イスク全体を表す。これより、ルート・ファイルシステム のためのデバイス・スペシャルファイルは 0S1 になる。 ディスクデバイスには、プロック・スペシャルファイル とキャラクタ・スペシャルファイルがある。両者は同し名 UNIX MAGAZINE 1991.6 UNIX ファイルの復元■ 前だが、 / dev 下の別々のサプディレクトリに置かれる。プ ロック・スペシャルファイルは / dev / ホんに格納され、キ ャラクタ・スペシャルファイルは / dev / S んに格納され る。キャラクタ・デバイスドライバは raw デバイスドライ バとも呼ばれる。これは、キャラクタ・テンヾイスドライバ がバッファリングされていないためである。そこで、ディ レクトリ名が r 赤々なのである。 キャラクタ・テンヾイスドライバはバッファリングされて いないので、読取りと書込みは全プロックに対しておこな われなければならない。一方、プロック・テンヾイスドライ バはデータのバッファリングをおこなうので、プロセスが 一部のプロックにアクセスすることができる。また、対応 するキャラクタ・スペシャルファイルとプロック・スペシ ャルファイルは同しデバイスに結びつけられるので、どち らも同しメジャーデバイス番号とマイナーデバイス番号を もっことになる。 指定されたファイル・ディレクトリをそのファイルシス テムから読み取るには、ファイルシステムのデバイスファ イル名がなんらかの方法で得られなけれはならない。 stat システムコールは、ファイルシステムのデバイス id を提 供するので第 1 段階としてはよい。しかし、いかにしてこ れからファイル名を導くかがはっきりしない。この答は、 固定ディスクのマイナーデバイス番号がどのように作成さ れているかということにある。 SystemV/386 では、マイ ナーデバイス番号のピット 0 ~ 3 にパーティション番号が、 ピット 4 ~ 5 にドライプ番号が、そしてピット 6 ~ 7 にコ ントローラ番号が含まれている。ほかのシステムの方法も 似通っているが、これは明らかに可搬性がいちしるしく低 いと考えられる。このためデバイス id とファイル名の変換 は、次ページのリスト 1 に示した関数 devtonam および namtodev のなかにまとめられている。 前述したように、 bat はファイルシステムから i ノード を直接読み取ることによってのみ得られる。リスト 2 ( 113 ページ ) に getdinode 関数を示す。これは、 ここに小した 原理と技法を用いて、ファイルのパス名だけが与えられた マウント中のファイルシステムからディスク i ノードを読 み取るのに使う。このために getdinode 関数は、 statfs を 用いて論理プロックサイズを、 stat を用いてデバイス id と i ノード番号を取得し、 devtonam を用いてデバイス id をデバイスファイル名に変換する。 i ノードはプロックの 111

UN Ⅸのもっとも特徴的な機能の 1 つは、標準で装備さ れている一群のユーティリティである。しかしこれらのな かには、削除されたファイルを復元させるツールはない。 この手抜かりによって、長年にわたり多くの悲喜劇が生ま れた。この間題の解決に大きな障害があるのは事実だが、 それでも UNIX のファイルを復元するユーティリティが 作成できないわけではない。 ロ UNIX ファイルの颱 UNIX のファイルシステムは、インデックス・ノード ( 通 常は i ノードと略される ) と呼はれる構造に集約される。 i ノードは、ファイルとデータブロックへのホインタに関す S_ISUID / * 実行時のユーザー id を設定 * / S_IGUID / * 実行時のグループ id を設定 * / UNIX フⅵルの復元 by Lyle Frost •from 凵 NIX REVIEW に分類される。また、このはかにもいくつかのモードフラ 3 っすつの 3 グループ ( 所有者、グループ、その他の権限 ) ファイルモードは 9 つのアクセス権限を含み、それぞれ よって作成される。 mknod ( 名前付きパイプ ) または pipe( 名前なしパイプ ) に プには固定数のデータブロック ( 通常は 10 ) がある。これは を換えれば、 fifo とは要するにパイプである。現在、パイ mknod システムコールによってのみおこなわれる。言葉 い。これらの作成は、 creat や叩 en によってではなく スポイントであり、それに関するデータは保持していな ック・スペシャルファイルはデバイスドライバへのアクセ 、ゝるすべての管理情報を含んでいる。キャラクタおよびプロ グがある。 s_lsvrx / * 実行後にスワップされたテキストを保存 (sticky ビット ) * / S / * レコード・ロッキングを強制 * / uid フィールドと gid フィールドは、ファイル所有者の ューサー id とグループ id の数値を含んでいる。これらの 値は、そのファイルにアクセスしようとするプロセスに対 して、 3 種類の権限のうちのどれを適用するか決めるため に使用される。プロセスのユーサ、一 id が uid フィールド と一致した場合には、所有者の権限が適用される。これが 一致せす現在のグループ id が gid フィールドと一致した 場合には、グループ権限が適用される。どちらも一致しな い場合には、その他の権限が適用される。 実際のプロセスには 2 セットの id がある。実 id と実効 id である。ファイルアクセス権限を決定するために使用さ れるのは実効 id である。実効 id と実 id は通常は同しにな っている。しかし、 set-user-id ビット (S-ISUID) がセッ 108 トされているプログラム・ファイルが実行された場合、プ ロセスの実効ューサー id としてそのファイルの所有者の ューザー id がセットされる。 set-group-id ピットがセッ トされている場合には、実効グループ id に同様のことが起 こる。このように設計されているのは、ファイルに直接ア クセスできないユーサーが、実行可能なプログラムからそ れらのファイルにアクセスできるようにするためである。 たとえばこれを使用して、データベース・ファイルに対す る不正な操作を防ぐことができる。 ⅲ ink フィールドのなかには、ファイルに対するリンクの 数が格納されている。すなわち、ディレクトリ階層内でそのフ ァイルを参照する名前の数である。 UNIX のディレクトリは、 基本的にはファイル名を i ノード番号に変換するために使用 UNIX MAGAZINE 1991.6

ァイルに対しても使用できることである。矢斤は、ユーザ ーがたくさん指示を出さなければならない点である。フリ ーリストは last-in-first-out なので、指定されたファイ ルからのすべてのプロックは同しグループになる。しかし、 ューサーは目的のファイルを含んでいるフリーリストのセ グメントを指定しなければならない。復元されるファイル が最後に削除されたファイルである場合 ( とくにファイル サイズが分かっているとき ) には、比較的単純である。しか し、フリーリストのすっと前のほうのファイルを復元する には、試行錯誤を繰り返さなければならない。初期化され ていないプロックがあると、問題はさらに複雑になる。と いうのは、プログラムはもはや間接プロックを自動的に破 棄できないからである。 どちらの方式を採用しても、システムがフリーリストを 使ってフリープロックを把握している場合にはリンクプロ ックのすくなくとも一部は上書きされてしまうので、デー タがいくらか失われることは避けられない。どれほどのデ ータが失われるかは、リンクプロックがたまたまデータで あったか、間接プロックであったかによる。もし間接プロ ックであった場合、フリーリスト方式ではデータはまった / #define BADIRC #def ine BATELMC 、ゝく失われない。しかし bat 方式では、上書きされたアドレ スを介してアクセスされていたすべてのプロックが失われ る。ピットマップを使用しているシステム上では、ファイ ルを完全に復元することができる。 ロ 設 ndel ユーティリティ リスト 3 に、 bat 方式のファイル復兀ユーティリティの コードを示す。復元は、 del と undel の 2 つのプログラム によっておこなわれる。 del プログラムの操作は rm と同 しであるが、各ファイルを削除する前に復元に必要な情報 を保存する。各ューザーはこの情報を保存しておくための ファイルを、自分のホーム・ディレクトリに置く。 undel プ ログラムは del によって削除されたファイルを復元する。 ローカルヘッダ del. h 、 syscalls. h 、 unixlib. h の内容はリ ストしていない。これらはそれぞれ論理定義、システムコ および標準 UNIX ライプラリ関数宣言を含ん ーノレ旦、 でいる。 こで、ほかのシステムに移植するためのいくっかのマ クロを定義しておく。 #define BATEI. MSIZ #define BI. KELMSIZ ( 1 の ( 13 ) ( 3 ) ( 4 ) #def ine #define / * bat 直接プロック数 * / / * bat 要素数 * / / * bat 要素サイズ * / / * 間接プロック要素サイズ * / memcpy(&(addr) , (char * ) (buf) + (n) * BATZMSIZ, BATELMSIZ) ; memcpy(&(addr) , (char * ) (buf) + (n) * BI. KELMSIZ , BLK%MSIZ) ; getbataddr(addr, buf (addr) = 0 ; getbataddr(addr, buf (addr) = 0 ; 上に示した設定は lnteractive Systems 386 / ix 用であ り、フリーリストではなくてピットマップを使用する。し たがって、完全にファイルを復元できる。これらのマクロ の大部分は自明であるが、間接プロック内のプロックアド レスは bat 内のものと同サイズであるとはかぎらない。こ のため、マクロ BATELMSIZ と BLKELMSIZ を分け てある。また、 bat と間接プロックからアドレスを抽出する コードは、アドレスのサイズとバイト順序の違いによりポ ータブルではない。したがって、これらの算出はマクロ getbataddr や getblkaddr のなかに隔離されている。保 存されている正確な復元情報は、 delfil ストラクチャ内に 114 見られる。 UNIX MAGAZINE 1991.6 これは、次の一連のコマンドでできる。 れはならない。 ければならす、 set-user-id ピットがセットされていなけ しなければならない。したがって、その所有者は root でな で、実効ューザー id をスーパーユーザーのものにして実行 del は i ノードをファイルシステムから直接読み取るの . del に保存する。 にそのファイルのためのエントリをファイル $ H 〇 ME / したとしよう。このプログラムは、ファイルを削除する前 こで、 rm の代わりとなる del というプログラムを作成