cwfs の研究

2012/10/20
2013/03/14 更新
2013/03/28 更新
2013/04/02 更新
2013/04/10 更新
2013/04/24 更新

2012年の夏休みは、9front の cwfs を試していた。cwfs は fscache と fsworm で構成されているが、fsworm の方から調べることとした。fsworm の方に関心がある理由は、ファイルの履歴等の情報は fsworm に置かれ、また fscache がクラッシュした時のリカバリーも fsworm に基づいて行われるからである。
もちろん、いかなるデバイスもやがては死を迎える。fsworm に対してもバックアップが必要である。cwfs 自体を RAID に置くことも考えられようが、僕には大げさすぎる。もう一つ HDD を追加して、そこに fsworm のコピーを持ちたい。それでは、どのようにコピーすれば、短時間でやれるのか? この問題を解明したかったのである。

9front 付属の cwfs は cwfs64x である。そこで、ここでは cwfs64x に基づいて解説する。

注意: この記事は今のところ筆者のメモに過ぎない。もちろん、誤りを含んでいるかも知れない。誤りを発見したら知らせていただければ幸いである。

cwfs とは

この節は未完成である。暇な時に書く事とする。

Sean Quinlan (Ph.D)
Ken Thompson (Ken's fs)
Plan9 2nd edition (1995)
Geoff Collyer (2007/03/27 mail)
9front (2011)
過去の履歴
WORM (write once read many)
消えない(消せない)
dump

Mac/OSX の time machine との比較
pdumpfs

以前はサーバのために1台を割り当てていた。
memory: ファイルサーバ専用機の中のメモリー
disk: disk cache
WORM: 光ディスク

現在は Plan9 の基で動くユーザープログラム cwfs
ユーザプログラムである事の利点: 仕組みを調べやすい。
memory: cwfs daemon 中のメモリー
disk: ファイルサーバの fscache パーティション
WORM: ファイルサーバの fsworm パーティション

cwfs (or cwfs32)
cwfs64
cwfs64x

cwfs console

概要

cwfs に関する僕のパーティションのサイズは次の通りである。

term% ls -l /dev/sdC0/fs*
--rw-r----- S 0 arisawa arisawa  22848146432 Sep 13 09:50 /dev/sdC0/fscache
--rw-r----- S 0 arisawa arisawa 114240734208 Sep 13 09:50 /dev/sdC0/fsworm
term%

cwfs コンソールはコマンド

con -C /srv/cwfs.cmd

で使えるようになる。

注意: ウィンドを新たに1つ作って

cat /srv/cwfs.cmd

を実行しておいて、他のウィンドウから

echo statw >> /srv/cwfs.cmd

を実行してもよい。配布版はこの方法を想定していると思われる。

cwfs コンソールで statw を実行すると、fsworm の利用統計が出力される。次にその出力例を示す。

> statw
cwstats main
	filesys main
		maddr  =        3
		msize  =    10313
		caddr  =     1035
		csize  =  1392255
		sbaddr =  1755217
		craddr =  1755389  1755389
		roaddr =  1755392  1755392
		fsize  =  1755394  1755394  0+25%
		slast  =           1754642
		snext  =           1755393
		wmax   =  1755392           0+25%
		wsize  =  6972701           1+ 0%
		  8600 none
		230005 dirty
		     0 dump
		1153555 read
		    95 write
		     0 dump1
		cache 17% full
>

図fig:statw>. cwfs コンソールでの statw の出力例。
プロンプト “>” は、オフィシャルな配布版では出ない。
筆者による修正版で出るようにしている。

maddr から wsize までの、等号の右の数字(1列目と2列目)は、サイズを表している。1列目の数字の情報は、fscache の Tcache block (block address 2) から得られる。2列目は fsworm から得られる^注1。これらの単位は msize を除けば block である。msize だけは bucket 数である。

注1: この部分は正しくない。2列目も fscache から得られている。fsworm の最後の super block の cache が fscache の中に含まれ、これを表示している。fsize を除いて、2列目の情報は、最後の super block から得られる情報と一致している。fsize は statw コマンドを実行した時点での値であり、これは fscache の Tcache block から得られる fsize と一致している。(2013/04/24)

fsworm には、fsworm のパーティションサイズに関する情報は含まれない事に注目しよう。fsworm が満杯になった時に、もっと大きなパーティションに置き換えられる可能性があるので、その場合には、単に満杯になったパーティションの内容を新しいパーティションにコピーすればよいように設計されているのであろう。

fscache も fsworm も block を単位として管理されている^注2。cwfs64x の場合には 1 block は 16KB である。以下、block をアドレスで表すこととする。ba[0] は最初の block を ba[1] は第2 block を意味する。

wsize の 6972701 は /dev/sdC0/fsworm の大きさを block 数で表している。

6972701*16*1024 == 114240733184

これは実際の /dev/sdC0/fsworm の大きさ 114240734208 よりも 1024 だけ少ないが、block を単位として使用されている為に、使用できない領域が発生したのである。

fsworm にはフォーマットの概念が存在しない事に注意すべきである。なぜなら Write Once だから、フォーマットしたらデータを書き込めない!^注3

fsworm には先頭 block から順に書き込まれる。snext (next super block) は、次に書き込まれる block を示している。dump を行うと、最初に super block と呼ばれる block が書き込まれ、それに続いてデータの本体が書き込まれる。Super block は、dump 毎の境界として、fsworm においては基本的な役割を果たしている。

sbaddr (super block address) は、最後に書き込んだ super block のアドレスである。また、slast は、その1つ前の super block のアドレスである。

注2: cwfs が管理する block は、ドライバが管理する読み書き単位としてのブロックとは別のものである。
注3: 最近では本来の意味での WORM を使う事はないであろう。バックアップメディアとしての光ディスクの存在意義は無くなっており、ハードティスクで WORM を代用する方が低コストで、かつ使い勝手も良い。以下の解説もハードディスクの使用を前提としている。

fsworm のバックアップ

2013/03/06 改訂

fsworm は(その仕組み上)非常に堅牢ではあるが、それでもハードウェアクラッシュによるデータ消失のリスクを負っている。バックアップを行うには、fsworm のコピー(例えば fsworm-bak)を持てばよい。

dump 毎に、fsworm の中に新たに生成された block だけをコピーして行けばよいと考えるかも知れないが、話はそんなに簡単ではない。なぜなら、書き込まれていない block が最後に dump された super block の下に存在するからである。筆者の観察ではそれらには2種類ある。
(a) reserved block^注1
(b) free block
である。
(a)は、fscache の中で使用されているが、まだ dump が完了していない fsworm の block である。
(b)は、今後 fscache が使用可能な fsworm の block である。

注1: “reserved block” は筆者が勝手に使っている用語である。この用語は文献には存在しない。

fsworm の構造

Block

fscache も fsworm も block を単位として管理されている。cwfs64x の場合には 1 block は 16KB である。以下、block をアドレスで表すこととする。ba[0] は最初の block を ba[1] は第2プロックを意味する。共に、先頭の 2 block は特殊である。block のアドレスは 8 B のデータで指定される。プログラムの中ではデータ型が Off で示されている。

fscache の場合には、ba[0] には config 情報が置かれている。ba[1] は使われていないようである。
fsworm の場合にも先頭の 2 block が使用されている気配はない。

どの block も Tag を持っている。もっとも、全ての block がフォーマットされているのではない^注1。

Tag の大きさは、cwfs64x の場合には 12B であり、block の末尾に置かれる。その構造は次のようなものである。

struct	Tag
{
	short	pad;		/* make tag end at a long boundary */
	short	tag;
	Off	path;
};

pad の値は 0 である。tag が block の種類を表している。 path の値に関する考え方は tag 毎に異なる。

16KB から Tag の 12B を除く領域がデータ領域(以下、Data で表す)であり、block の種類毎の構造を持っている。纏めると

block = Data + Tag

である。

注1: 最近の HD は容量が大きい。もしも全ての block をフォーマットすると膨大な時間を要する。さらに言えば、WORM デバイスはフォーマットすれば書き込めなくなる!

dump stack

2013/02/28

dump を繰り返すと、fsworm には、ダンプしたデータが積み重ねられる。データは決して上書きされることはない。その様子を図fig:dumpblock>(左)に示す。

以下、block address n の block を ba[n] で表す。ba[0] と ba[1] は使われていない。cwfs が実行されると、最初に 3 つの block

ba[2]: super block
ba[3]: cfs root block
ba[4]: dump root block

が作られる。この中には fscache の中に含まれるファイルの情報は含まれていない。

注意: “cfs root block” とか “dump root block” とかの言葉は正式なドキュメントやプログラムコードの中には現れない。 “cfs root address” と “dump root address” は現れる。

dump 毎に block が積み上げられる。1回の dump で積み上げられる block を単に dump と呼ぶ事にする。1つの dump の中には必ず3つの block, “super block”, “cfs root block”, “dump root block” が含まれる。図fig:dumpblock>(右)には、dump の内部構造が示されている。

super block と cfs root block の間の block には、fscache の内容が(前回の dump から更新された差分だけ)保存される。

cfs root block と dump root block の間の block には、dump された年月日の情報が含まれる。必要な block 数は dump の回数に依存する。

Super Block

fsworm の構造を捉える上で、もっとも基本的なのは super block である。super block の tag は Tsuper(=1) である。cwfs のコードを読むと、super block の Tag の中の path は、QPSUPER(=2) となっている。

super block は、fscache をダンプした時に 1 つ作られる。まず super block が fsworm に書き込まれ、続いてデータの本体が block 単位に書き込まれる(図fig:dumpblock>右)。

super block の構造は

struct	Superb
{
	Fbuf	fbuf;
	Super1;
};

を持つ。

Fbuf は free block のアドレスの配列を内部に保有している。free block に関する解説は後回しにする。

Super1 が重要である。

struct	Super1
{
	Off	fstart;
	Off	fsize;
	Off	tfree;
	Off	qidgen;		/* generator for unique ids */
	/*
	 * Stuff for WWC device
	 */
	Off	cwraddr;	/* cfs root addr */
	Off	roraddr;	/* dump root addr */
	Off	last;		/* last super block addr */
	Off	next;		/* next super block addr */
};

図fig:super1>. Super1 の構造

ここで分かるように、各々の super block は、次の super block のアドレス(next)を保有している。そして最初の super block は ba[2] から始まる。従って ba[2] から順に super block を辿れば、次にダンプされるアドレスが分かることになる。次に、その出力結果例を示す。(このツールは後に紹介する)

super blocks:
2
5
69908
85793
104695
222009
...
1751346
1754278
1754381
1754569
1754642
1755217
1755393

最後の 1755393 は、次に作られる予定の super block アドレスである。ba[1755217] の中の Super1 の内容は(例えば)次のようなものである。

super1 fstart: 2
super1 fsize: 1755394
super1 tfree: 92
super1 qidgen: 6d76e
super1 cwraddr: 1755389
super1 roraddr: 1755392
super1 last: 1754642
super1 next: 1755393

これらの情報の一部は cwfs のコンソールからも得られる。

sbaddr 1755217: 現在の super block (最後に書き込まれた super block)
snext 1755393: 次のダンプ予定のアドレス(つまり、次に作られる予定の super block アドレス)
slast 1754642: sbaddr より一つ手前の super block アドレス

Directory Entry Block

2013/03/02 更新

次に基本的なのは directory entry block である。この block の Tag.tag は Tdir である。また、Tag.path は、親ディレクトリの qid に一致する。

directory entry block には次の directory entry (Dentry) が1個以上(cwfs64x の場合、最大62個)含まれている。

struct	Dentry
{
	char	name[NAMELEN];
	Userid	uid;
	Userid	gid;
	ushort	mode;
		#define	DALLOC	0x8000
		#define	DDIR	0x4000
		#define	DAPND	0x2000
		#define	DLOCK	0x1000
		#define DTMP	0x0800
		#define	DREAD	0x4
		#define	DWRITE	0x2
		#define	DEXEC	0x1
	Userid	muid;
	Qid9p1	qid;
	Off	size;
	Off	dblock[NDBLOCK];
	Off	iblocks[NIBLOCK];
	long	atime;
	long	mtime;
};

図fig:dentry>. Directory entry

ここにはファイルやディレクトリの名前(name)が含まれているので、Dentryのサイズは許容する名前の長さ(NAMELEN-1)に依存する。

dump root block は directory entry block の 1 つである。筆者の家庭でのシステムの場合には次のように dump した日付が見える。

term% ls /n/dump
/n/dump/2012/0801
/n/dump/2012/0802
/n/dump/2012/0804
/n/dump/2012/0813
....
/n/dump/2013/0121
/n/dump/2013/0127
/n/dump/2013/0128
/n/dump/2013/0205
....

最初の行は初めて dump を行った時に(2012年8月1日)生成されている。

ls -l /n/dump/2012/0801

を実行すると次のように、この日のファイルにアクセスできる。

maia% ls -l /n/dump/2012/0801
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/386
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/68000
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/68020
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/acme
d-rwxrwxr-x M 495 adm  adm  0 Jul 31  2012 /n/dump/2012/0801/adm
....
d-rwxrwxr-x M 495 sys  sys  0 Jan 18  2012 /n/dump/2012/0801/mnt
d-rwxrwxr-x M 495 sys  sys  0 Jan 18  2012 /n/dump/2012/0801/n
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/power
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/power64
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/rc
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/sparc
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/sparc64
d-rwxrwxr-x M 495 sys  sys  0 Jul 31  2012 /n/dump/2012/0801/sys
d-r-xr-xr-x M 495 sys  sys  0 Jan 18  2012 /n/dump/2012/0801/tmp
d-rwxrwxr-x M 495 sys  sys  0 Aug  1  2012 /n/dump/2012/0801/usr
maia%

図fig:ls_/n/dump>. ls /n/dump

dump した年月日情報 (YYYY/MMDD) は dump root address と cfs root address の間にある。(図fig:dumpblock>)

このケースでは次の図fig:dirent>に示すように block が繋がっている。

図fig:dirent>. directory entry block の繋がり

長方形が1つのブロックを表している。この図ではどれも directory entry block である。dump の回数がまだ少ないので、2013年の月日の情報は1個の directory entry block で間に合っているが、そのうちに複数の block が要求されるようになるだろう。

Plan9 では図fig:dentry>の Dentry 構造体を見れば分かるように、directory の名前と、mode などの情報が同じ block に同居している。他方 UNIX では mode などの情報は、inode に置かれ、名前の一覧とは別の block になっている(図fig:inode>)。この違いの起源は UNIX では hard link のサポートのために、link counter を名前とは別の block (具体的には inode) に持たなくてはならないからだと思える。

図fig:inode>. unix inode の概念
図で contents と書いたのは、file の中身であったり、他の directory であったりする。

Dentry の Qid9p1 構造体は

struct	Qid9p1
{
	Off	path;			/* was long */
	ulong	version;		/* should be Off */
};

であるが、この path は、mode がディレクトリの場合(つまり mode&DDIR != 0 の場合)には先頭ビットに 1 が立てられている。(このように設計した理由に関しては僕は今のところ解らない。) 正式な qid、すなわち、コマンド

ls -ql

で表示される qid は、この qid.path の先頭ビットを落としたもの、すなわち qid.path&~DDIR である。

cwfs64x の場合、1つの Dentry は 260 B である。従って、1つの block には最大 62 個の Dentry を保持できる。

name には、ファイル名やディレクトリ名が入る。NAMELEN は cwfs64x の場合には 144 である。名前は '\0' で終わるので、名前の最大長は 143 文字である。名前の他に、ディレクトリやファイルにとって基本的な情報がこの中に含まれている。

Dentry がファイルを表している場合(mode&DDIR == 0)、ファイルコンテンツの置かれている block は direct block (dblock[NDBLOCK]) と indirect block (iblocks[NIBLOCK]) を基に辿る事ができる。ファイルコンテンツを含む block は Tfile でタグ付けられている。

Dentry がディレクトリの場合(mode&DDIR != 0)には、そのディレクトリコンテンツ(中に含まれているファイルやディレクトリの情報)の置かれている block は、ファイルの場合と同様に、direct block (dblock[NDBLOCK]) と indirect block (iblocks[NIBLOCK]) を基に辿る事ができる。ディレクトリコンテンツを含む block は Tdir でタグ付けられている。

cwfs64x の場合には NDBLOCK の値は 6、NIBLOCK の値は 4 である。

6 個の direct block には、データが直接書かれる。1つの direct block には 16*1024 - 12 B のデータが書き込めるので、6 個の direct block には合計 6*(16*1024 - 12) B のデータを書き込める。ディレクトリの場合には 372(=62*6)個までの Dentry が扱える事となる。

Indirect Block

directory entry block の Dentry 構造体に含まれる iblocks[0] によって示される block には、

(16*1024 - 12)/8 = 2046

個の block アドレスが含まれる。ここの 8 は 1 個の block アドレスの大きさである。) これらの block アドレスは、データの場所(つまり direct block)を示している。従って

2046 * (16*1024 - 12) = 33497112 B

のデータを書き込める。このような block 情報を 1 次の indirect block と言うこととしよう。

iblocks[1] には、2 次の indirect block が書かれる。つまり、この block には block アドレスが書かれているのであるが、それらのアドレスは(データの場所ではなく) 1 次の indirect block アドレスである。従って

2046 * 2046 * (16*1024 - 12) = 68535091152 B

のデータを書き込める。

同様に、iblocks[2] には

2046 * 2046 * 2046 * (16*1024 - 12) = 140222796496992 B

そして iblocks[3] には

2046 * 2046 * 2046 *2046 * (16*1024 - 12) = 286895841632845632 B

となる。

indirect block のタグは

iblocks[0]	Tind1
iblocks[1]	Tind2
iblocks[2]	Tind3
iblocks[3]	Tind4

となっている。また、これらの Tag.path はどれも親ディレクトリの qid に一致する。

File Block

ファイルの内容を含む block は Tfile のタグが付けられている。この block の Tag.path は、このファイルが属するディレクトリの qid に一致する。

1つの file block には、最大

16*1024 - 12 B

のファイルデータを保存できる。

ファイルの内容は block 単位で管理されている。ファイルの内容が更新された時には全ての block が書き換えられるのだろうか? 筆者の実験によると否である。1ブロックよりも大きなファイルの末尾にデータを追加すると、最後の block だけが更新される。他の block は、そのまま利用される。もっとも、この実験は
(a) ファイルに append 属性を指定している
(b) ファイルの末尾に seek して書き込んでいる
のいずれかの条件の下で実験している。

16KB を超える大きなファイルをテキストエディタで開いて、末尾にデータを追加した場合には、完全に書き換えられると思う。(実験はしていないけど...)

書き換えられた block だけが新たに生成される cwfs の特性は、特にサーバで重要である。筆者のサーバではウェブのサーバのログファイルは 1.7GB にも上る。

1757143424 Oct 18 17:13 http

この大きさのファイルのコピーを毎日作り続けるわけには行かないであろう^注1。

注1: Mac/OSX の TimeMachine や Linux の pdumpfs では、ファイルが更新されていれば、そのコピーが新たに作られていく。ハードリンクだけで TimeMachine の機能を実現しようとすれば、コピーは不可避な仕様になるはずである。サーバでは、日々更新される大きなログファイルを抱え込むので、サーバー用途には全く向かないはずである。データベースファイルの場合には、cwfs と言えども日々の dump から外さなくてはならないだろう。トランザクションのログを採る方が安全である。

Fsworm Root

2013/03/09

fsworm の全ての情報は dump stack のトップにある dump root block から辿る事ができる。このアドレスは cwfs console の roaddr から知ることができる。図fig:ls_/n/dump>および図fig:dirent>は、ここから辿って見えるパスの最初の部分である。

実は roaddr は fscache が管理している root block であるが、fsworm の dump root block と一致している。

ダンプの順序

ダンプは現在の fscache に基づいて行われる。そして、まず最初に super block が fsworm に書き込まれる。これに続いて、ディレクトリツリーの末端の情報から順に書き込まれる。従って、fsworm の中に、例えば

/2012/0925/....

が作成される場合には、一番最後に /、その前に 2012、さらにその前に 0925 が...

qid

ユーザからは ls command に q option を添えてファイルやディレクトリの qid を見ることができる。例えば

maia% ls -ql
(000000000009baa2    6 00) --rw-rw-r-- M 326 web     web 33597 Mar  8 15:01 bucket.png
(000000000009baa3    3 00) --rw-rw-r-- M 326 web     web 13693 Mar  8 15:02 bucket.svg
(0000000000089b8c    2 00) --rw-rw-r-- M 326 arisawa web   782 Sep 28 10:11 console.txt
(0000000000089b8d    2 00) --rw-rw-r-- M 326 arisawa web  2401 Oct 15 21:21 cwfs.svg
...
maia%

のように表示される。先頭の ( ) の中の 16 進数表示の部分が qid であり、その次の数字が qid version である。
マニュアルによると qid はfile system の中でユニークであると言う。

ユニークであるならば、qid が管理されなくてはならない。super block の中の qidgen が、そのためにあると思える(図fig:super1>)。

実験をして見れば分かるが qid はファイル名の変更によっては変わらない。内容が変わると version が変わる。
そうであるから、エディタを作る場合には、保存時に他の何かによって変更を受けたか否かを知るために使えるのであるが、time stamp の方が手軽なので僕はこれまでに qid を利用した事は無い。(なお unix の qid は、違うものらしい)

fsworm や fscache の中を除くと、qid とその version は directory entry の中に含まれ(図fig:dentry>)、その contents に関する block が同じ qid となっていることが分かる。つまり block の所属を確認するために使われていると思われる。

fscache の構造

ba[0]	config
ba[1]	-
ba[2]	Tcache

ba[maddr]	map
...
ba[caddr]	cache
...

Config Block

2013/03/05

cwfs64x を見る限り、筆者の config block (ba[0]) には、テキスト形式で次のようなデータが先頭から書き込まれていた。(この内容は cwfs console の printconf コマンドでも見える)

service cwfs
filsys main c(/dev/sdC0/fscache)(/dev/sdC0/fsworm)
filsys dump o
filsys other (/dev/sdC0/other)
noauth
newcache
blocksize 16384
daddrbits 64
indirblks 4
dirblks 6
namelen 144

noauth は、認証をしないで cwfs へのアクセスを許す事を意味している。noauth は安全な環境での実験レベルでしか許されない特殊な設定である事に注意すべきである。
大学で使っているのは、今年の2月の版であり、これは noauth にはなっていない。(2013/04/10)

さらに、この block は次のように tag 付けられている。

pad: 0000
tag: 10 (Tconfig)
path: 0

ソースコードには、次の構造化データがある。

struct	Conf
{
	ulong	nmach;		/* processors */
	ulong	nuid;		/* distinct uids */
	ulong	nserve;		/* server processes */
	ulong	nfile;		/* number of fid -- system wide */
	ulong	nwpath;		/* number of active paths, derived from nfile */
	ulong	gidspace;	/* space for gid names -- derived from nuid */

	ulong	nlgmsg;		/* number of large message buffers */
	ulong	nsmmsg;		/* number of small message buffers */

	Off	recovcw;	/* recover addresses */
	Off	recovro;
	Off	firstsb;
	Off	recovsb;

	ulong	configfirst;	/* configure before starting normal operation */
	char	*confdev;
	char	*devmap;	/* name of config->file device mapping file */

	uchar	nodump;		/* no periodic dumps */
	uchar	dumpreread;	/* read and compare in dump copy */
	uchar	newcache;
};

この中のデータは、初期化過程の中で、cwfs の種類毎に(ソースコードの中で)与えられている。

Tcache Block

Tcache block は cwfs に関する基本情報を管理している。この内容は cwfs コンソールで見ることができる。

struct	Cache
{
	Off	maddr;		/* cache map addr */
	Off	msize;		/* cache map size in buckets */
	Off	caddr;		/* cache addr */
	Off	csize;		/* cache size */
	Off	fsize;		/* current size of worm */
	Off	wsize;		/* max size of the worm */
	Off	wmax;		/* highwater write */

	Off	sbaddr;		/* super block addr */
	Off	cwraddr;	/* cw root addr */
	Off	roraddr;	/* dump root addr */

	Timet	toytime;	/* somewhere convienent */
	Timet	time;
};

fscache の各ブロックはメモリーにキャッシュされている。10秒毎にメモリーのキャッシュは、(更新があれば) fscache に書き込まれる。

Mapping

2013/03/08 更新

fsworm の各 block は、図fig:fscache>の cache area の cache block に mapping される。

fscache の cache block のアドレスを cba とすると cba は

caddr <= cba < caddr + csize

の範囲にある。fsworm の 0 から wsize の block が fscache のこの領域に map される。

cache block の総数は(cwfs コンソールでは) csize で表示されている。caddr から始まる、残りの全ての block が cache block ではない事に注意する。

筆者のシステムの例では fsworm の block 数は 6972701 であるのに対して、fscache の cache block 数は 1392255 である。従って 1/5 程度のキャッシュ能力を持っている。また、fscache には 1394540 個の block が採れるが、実際に使われているのは、1035+1392255(=1393290) に過ぎない。未使用領域は 0.1% 程度である。

単純に考えると表tab:mapping>に示すような mapping を思い浮かべるかも知れない。

表tab:mapping>. a simple but problematic mapping from fsworm to cache

ここに、cache と書いたのは fscache の cache area である。示されている address は caddr から数えている。

しかし、この mapping は問題を孕んでいる。ある fsworm block が cache されていると、同じ cache block に map される他の fsworm block が cache に入り込めない場合がある。

そこで cwfs では、間に bucket をかませて、mapping に柔軟性を持たせている。その様子を表tab:bucket>に示す。

説明を容易にするために fsworm の block address を wa とし、caddr から数えた cache の address を ca とする。wa%msize が同一の wa は ca%msize の ca のどれかに map されると考えるのである。実際の mapping の状態は fscache の map block にある bucket によって管理されている。

bucket

fscache の maddr から caddr までの block は map block で、その tag は Tbuck である。map block は bucket の集まりで、bucket には cache の状態と、対応する fsworm の block address が含まれている。

各 bucket は次の構造を持っている。

struct	Bucket
{
	long	agegen;		/* generator for ages in this bkt */
	Centry	entry[CEPERBK];
};

各 map block は最大 BKPERBLK(=10) 個の bucket を保有できる。

fscache に含まれる bucket の総数は msize で与えられている。以下、bucket に block address の小さい方から順に 0 から msize - 1 までの番号を付け、それを bucket address と言う。

cache entry

各 bucket は CEPERBK(=135) 個の Cache Entry を持っている。各 Cache Entry は、現在のマップの状態を表している。

struct	Centry
{
	ushort	age;
	short	state;
	Off	waddr;		/* worm addr */
};

fsworm の block address ba から、対応する fscache の block address cba を見つけるには、まず

bn = ba % msize

を計算する。そして bucket[bn] の中の 135個の cache entry の waddr を調べる。もしも、fsworm の block address ba の block が cache されていれば、その中に ba と一致するものが存在するはずである。この cache entry を entry[ce] とすると、

cba = msize*ce+bn+caddr

で求める事ができる。詳しくは「Map from Worm to Cache」で解説する。

逆に、現在 cache されている fscache の block address cba から fsworm の block address ba を求めるには、まず

bn = (cba - caddr) % msize  # bucket addr
ce = (cba - caddr) / msize  # entry addr

を計算すれば bucket address bn が求まるので、その中の cache entry ce のwaddr を見ればよい。

fscache の cache area の block は cache entry によって「状態」を保有していることになる。以下、cache block の状態は◯◯であるとか、cache block に対応する worm address は◯◯であるとか言う事にする。

age

age は、cache block の古さを表している。小さい値が古い。だから概念的には age と言うよりも birth day に近い。新たに cache する必要が発生した場合には、(Cnone が存在しない場合には)age の小さい cache が優先的に捨てられる。そして bucket の agegen の値が新たに割り当てる age の値となる。cache にデータが割り当てられれば agegen が 1 つ増加する。age の最大値 MAXAGE=10000 が存在する。それを超えた時には、age の再割当が必要になるはずであるが、詳細はコードをよく読んでいないのでわからない。

state

cache の state とは、対応する Centry の状態で、次の値を持つ。

Cnone  = 0
Cdirty = 1
Cdump  = 2
Cread  = 3
Cwrite = 4
Cdump1 = 5

cache されていない cache block の状態は Cnone になっている。僕の観察では、この場合の waddr はゴミであり意味を持っていないように思える。

worm からデータを読み取った cache の場合には、waddr は元の worm の address そのものである。cache の状態は Cread になっている。この場合には cache block の内容は対応する fsworm の block と同じである。(キャッシュであるから当然の事)

既存の directory や file が変更を受けると、その cache の Cread のタグが Cwrite に変化する。そして waddr は変更を受けない。もちろん dump 時に上書きするわけには行かないのだから、その時には新しい worm address に保存され、同時に cache entry の中の waddr も更新されるはずである。異常なく dump されると状態は Cread になるであろう。

新たに directory や file を作成した場合には、その cache block に対応する wba には worm の未使用の address が割り当てられる。状態は Cdirty になる。dump が完了すると Cread になっているはずである。

状態 Cnone と Cread の cache は、waddr に変更を反映させる必要は無い。従って、この Centry に対応する fscache の block は(必要に応じて)捨てても構わないことを意味している。

ところで cwfs コンソールの statw コマンドを実行した時の

		  8600 none
		230005 dirty
		     0 dump
	       1153555 read
		    95 write
		     0 dump1

では Centry を直接調べて、state の値の分布(個数)を表示している。

free block and dirty block

2013/03/11
2013/03/14 改訂
2013/03/29 訂正
2013/04/10 追加

次のように分類するのが良い。
(a) unwritten block
(b) dirty block
(c) free block

(a) の unwritten block とは dumped area の中に存在する、未書き込みの block。
(b) の dirty block とは fscache の中で Cdirty とされている block。cwfs は、新たに file や directory を作成する時に、cache に worm の address を対応付け、cache の block の状態を Cdirty とする。この worm address は未使用アドレスであり、unwritten block が使えるなら、それを使う。
dump 直後には

(a) ⊇ (b)

である。
(c) の free block とは dirty block のうち、fscache に free block として登録されている block。これらは file tree に link されていない。link されている dirty block は dump の対象となるが、link から外れた block は dump されない。cwfs はこれらをゴミとして捨てるのではなく、新たに dirty block を作る時に利用する。
cwfs は free block の list を持っている。free block list は supper block の中と、fscache の Tfree で tag 付けられた block に存在する。supper block および Tfree block には 2037 個の block address 情報を保持できる。
従って

(b) ⊇ (c)

である。

fscache の Cwrite の状態の block は、実際に dump される時に初めて dump 先の address が確定する。これらの address は最後の dump の上に積み上げられる。他方 Cdirty の状態の block には、取りあえず fsworm の address と関係付けられる。

そもそも free block など発生させないように巧くやれないのか? いろいろ考えるが、結構難しそうである。file や directory の削除が問題である。dump が毎日朝5時に行われるとしよう。昼間の作業でいくつかの directory や file を新たに作ったとする。それらを C1,C2,...,Cn とする。fscache 内のこれらの block はどれも Cdirty の状態に置かれ、fsworm の address と関係付けられる。これらの内のいくつかはその日の内に削除されることもあるだろう。削除されたものを D1,D2,...,Dm とする。C1,C2,...,Cn から D1,D2,...,Dm を差し引いた部分が dump されるのであるが、dump で生成される fsworm の address が連続している事は期待しがたく、「穴」を持つ事となる。それらは free block として将来の利用のために予約されるはずである。

もちろん、削除した file や directory は直ちに親 directory の entry から削除されるが、その contents の状態は Cdirty のままになっている。

Cdirty 問題は僕にはまだ分からない事が多い。僕の fscache は大量の Cdirty block を抱えている。どうやら、この状態は異常らしい。原因は何か? 考えられるのは cwfs console の clri コマンドで大きな directory を削除したあとに、check free コマンドを行わなかった事。rm コマンドによってファイルを削除した場合には、不要になった block は free block list に入って行くが、clri の場合には入らないらしい。それらは利用されない block として捨てられるらしい。

super block には free block list を持ち、2037 個の free block を登録できる。これを超えた free block の address は、Tfree でタグ付けられた fscache の block に記録されている。Tfree block は super block と同様に free block list を持っている。free block list の構造体は両者とも同じである。

super block や Tfree block に含まれる free block を free[n] (n=0,1,...) とする。ソースプログラムを追って行くと、free[0] は特殊であることが分かる。これは Tfree block への pointer なのである。もっと正確に言えば、free[0] に対応する fscache の address が Tfree block になっているはずである。(図fig:freelist>)

msize と csize

msize 個の bucket の中には msize*CEPERBK 個の cache entry が存在する。筆者のケースでは、msize が 10313 なので、この計算結果は 1392255 となる。この数字は csize に一致する。つまり、

csize = msize*CEPERBK

の関係が成立する。1つの Cache Entry は 1つの cache block を管理しているのである。

msize 個の bucket を収納するには、

(msize+BKPERBLK-1)/BKPERBLK

個の block が必要である。割り算の形が複雑なのは、切り上げているからである。筆者のケースでは、msize が 10313 なので、この計算結果は 1032 となる。これに maddr の 3 を加えて、caddr の 1035 と一致する。つまり、

caddr = (msize+BKPERBLK-1)/BKPERBLK + maddr

の関係が成立する。

Map from Worm to Cache

bn を bucket address、ce を、その bucket の中の cache entry のアドレスとする。bn と ce は次の範囲にある。

0 <= bn < msize
0 <= ce < CEPERBK

bn と ce を基に、cache block address を対応させなくてはならない。
2つの自然な考え方がある。
(a) bn*CEPERBK+ce+caddr
(b) msize*ce+bn+caddr
もちろん他のもっと複雑なマッピングは考えられるが、それらを採用する理由は存在しない。
そして、実際には後者の方式(b)が採用されている。

前者は採用しがたい。なぜなら、ファイルは fsworm の連続した block を占める傾向がある。従って (a) を採用したならば、新たに作成された大きなファイルのキャシュ情報は1つの bucket を占有することになる。するとその bucket が管理する cache block には、(fsworm に dump しない限り)新たにキャッシュできなくなる。

さらに後者の場合には、fsworm の連続した block をキャッシュした場合に、fscache でも連続した block になる可能性が高いところにある。(ハードディスクの seek time が節約できる。)

msize の決定アルゴリズム

msize はどのような計算で決定されるか?
map block と cache block の合計数を m とすると、
map block を n 個にした場合の可能な m-n(=csize) の値は、

(n-1)*BKPERBLK*CEPERBK < m - n <= n*BKPERBLK*CEPERBK

を満たす必要がある。つまり、

1.0*m/(1 + BKPERBLK*CEPERBK) <= n < 1.0*(m + BKPERBLK*CEPERBK)/(1 + BKPERBLK*CEPERBK)

を共に満たす必要があるが、そのような n は

n = (m + BKPERBLK*CEPERBK)/(1 + BKPERBLK*CEPERBK)

で得られる。すなわち、

m - n = ((m - 1)*BKPERBLK*CEPERBK)/(1 + BKPERBLK*CEPERBK)

このように計算された m-n は CEPERBK の倍数である保証が無い。従って次の補正を加える必要がある。

msize = (m-n)/CEPERBK
csize = msize*CEPERBK
caddr = (msize + BKPERBLK - 1)/BKPERBLK + maddr

で計算される事になろう。

筆者の fscache は

1394540 block

確保できるので、

m = 1394540 - 3 = 1394537

である。この計算方式によれば

msize = 10322
caddr = 1036
csize = 1393470

となり、caddr + csize は 1394506 である。これは fscache の block 数 1394540 よりも小さいので、これで良いはずなのであるが、実際の cwfs の値は違う。実際には、この msize をさらに調整し

msize = maxprime(msize - 5)	# Ken's value
csize = msize*CEPERBK
caddr = (msize + BKPERBLK - 1)/BKPERBLK + maddr

としている(cw.c)。ここに maxprime(n) は、n を超えない最大の素数である。この調整が何故必要なのか? 筆者には不明である。(fsworm と fscache との関係では、この調整は不要なはずである。)

Fscache Root

2013/03/09

fsworm が root を持つように、fscache も root を持っている。(持たなければ directory tree を辿れない)

fscache の root block の address は fsworm の dump stack top の dump root block の address を基にして、通常の mapping rule に従って決定されている。

Recovery

復元 (recovery)

2013/02/28 更新

cwfs に異常をもたらす原因はいろいろあるが、主なケースは次の2つであろう。
(a) 書き込み中の停電
(b) ハードウェアクラッシュ
これらはさらに、様々なケースで細分化されるが、ここでは fsworm が健全である(あるいは同じようなことであるが、fsworm のバックアップが存在している)ことを仮定する。この場合には、fsworm に基づいて復元することになる。

以下の仮定を置く:

/dev/sdC0/fscache
/dev/sdC0/fsworm

が存在し、

fsworm は健全であり、
fscache の先頭 block には正しい config 情報が含まれている。

その元では、cwfs のスタートで(9front では)

bootargs is (tcp, il, local!device)[local!/dev/sdC0/fscache]

のメッセージがでるので

local!/dev/sdC0/fscache -c

を input し、その後 config: の prompt に対して

recover main
end

で応えればよい。(復元は非常に早い。(1~2秒?)

fscache の先頭ブロックは、cwfs の活動中には書き込み対象から外されているので、ハードディスクが物理的損傷を受けていない限り、データのロスは高々、最後の dump 以降に限られると言える。

fscache の復元に必要な全ての情報が fsworm の block address 範囲 0 から snext までの中に含まれている。復元に際して、fsworm の全てを調べる必要は無い。最後にダンプした記録から辿る事ができる。この作業は cwfs が自動的に行うはずであるが、参考のために、fsworm の構造をもう少し詳しく解説する。

Plan9(あるいは9front)では、過去のファイルの状態は

9fs dump

を実行して

/n/dump

以下に見えるが、ここに見える全ての情報が次のダンプアドレス snext の1つ前の block アドレス (= roaddr = snext - 1) から簡単に辿って行くことができる。

後に紹介するプログラム cwstudy は、block アドレスを指定して、その内容を表示する。次は cwstudy の実行例である。

cpu% cwstudy 1755392
/dev/sdC0/fsworm
tag pad: 0000
tag tag: 11 (Tdir)
tag path: 1

name: /
uid: -1
gid: -1
mode: 0140555
muid: 0
qid path: 80000001
qid ver.: 0
size: 0
dblock: 1755391 0 0 0 0 0
iblock: 0 0 0 0
atime: 1343737574 // Tue Jul 31 21:26:14 JST 2012
mtime: 1343737574 // Tue Jul 31 21:26:14 JST 2012

最初に得られる名前は “/” である。作成日は、fsworm が作られた 2012年7月31日となっている。dblock[0] の 1755391 は、“/” の下の directory entry block のアドレスである。

cpu% cwstudy 1755391
/dev/sdC0/fsworm
tag pad: 0000
tag tag: 11 (Tdir)
tag path: 1

name: 2012
uid: -1
gid: -1
mode: 0140555
muid: 0
qid path: 80000001
qid ver.: 27
size: 0
dblock: 1755390 0 0 0 0 0
iblock: 0 0 0 0
atime: 1348729247 // Thu Sep 27 16:00:47 JST 2012
mtime: 1343797238 // Wed Aug  1 14:00:38 JST 2012

block アドレス 1755391 に含まれるディレクトリの名前は 2012 である。1つしか現れていないのは、fsworm の運用開始が 2012 だからである。

block アドレス 1755390 には多数の directory entry が含まれている。

term% cwstudy 1755390
[中略]
name: 0925
uid: -1
gid: -1
mode: 0140555
muid: 0
qid path: 80000001
qid ver.: 27
size: 0
dblock: 1755212 0 0 0 0 0
iblock: 0 0 0 0
atime: 1348584237 // Tue Sep 25 23:43:57 JST 2012
mtime: 1348584237 // Tue Sep 25 23:43:57 JST 2012

name: 0927
uid: -1
gid: -1
mode: 0140555
muid: 0
qid path: 80000001
qid ver.: 27
size: 0
dblock: 1755388 0 0 0 0 0
iblock: 0 0 0 0
atime: 1348729247 // Thu Sep 27 16:00:47 JST 2012
mtime: 1348729247 // Thu Sep 27 16:00:47 JST 2012

それらの名前は、ダンプした月日を表している。また、それらは

ls /n/dump/2012

で表示される名前と一致する。

さらに進んで、2012 の下にある 0927 の directory entry も同様に見つける事ができる。それらの名前は

ls /n/dump/2012/0927

で表示される名前と一致する。そこには adm や sys や usr などの名前が見えるだろう。

0925 の dblock[0] は 1755212 である。この block アドレスは 9月25日にダンプした block の中に含まれている。(この日には 1754642 から 1755216 までが消費された)

9月27日のダンプでは、この日のファイルを全て新たにコピーするのではなく、変更されていないコンテンツに関しては、古いコンテンツをそのまま使う。ここでは 0925 に関しては、9月25日のコンテンツがそのまま使われている。

fsworm では block 単位の差分法が使われているのである。(この件に関しては後にまた吟味する)

復元(recovery)について吟味

fsworm が健全であれば、super block を snext まで辿れば、snext を基に復元できる。では確実に snext まで辿れるのか?

fsworm が本当の WORM あるいは新品のハードディスクであれば問題はないであろう。snext の先に、Tag らしきデータは無いのであるから間違う余地は無い。しかし使い古しのハードディスクであればどうだろう?
Tag を頼りに super block を辿る際に、ゴミを Tag と勘違いするかもしれない。super block の Tag 構造体は

struct	Tag
{
	short	pad;		/* make tag end at a long boundary */
	short	tag;
	Off	path;
};

であり、pad は 0、tag は 1、path は 2 である。ゴミの中で、この 12Bが完全に一致する確率は 2^-96 で^注1、十分に小さいと考えるかもしれない。何しろ、fscache がクラッシュする確率自体、極めて小さくて、サーバのライフタイム(5年程度か?)の中に、あるか無いかだ。

しかし、こうした確率の計算は、ランダムなデータが書き込まれている事を前提にしている。この使い古しのハードディスクの fscache パーティションが、以前に fscache パーティションとして利用されていたものを、そのまま使ったらどうだろう? 誤認される確率は fsworm の中での super block の割合までに上がるので、無視できないかもしれない。従って、fscache のパーティションを作る場合に注意した方が良いだろう。(パーティションの先頭アドレスを少しずらすとか...)

fscache の Tcache block の中には fsworm の最後の super block との整合性を確認できる情報が含まれている。従って通常の recovery においてはこのような心配はいらないはずである。

注1: 実際には、tag と path だけで辿っているので、確率は 2^-80 である。この確率を小さくするためには、他に slast の情報を使う手もあろうが、そこまでの価値があるかは怪しい。

Recovery によって失われるもの

2013/03/28

free block で失われるものがある。 free block とは既に dump された領域に存在する、まだ書き込まれていない block である。cwfs は、ここに data を書き込む機会があれば書き込もうとする。記憶スペースを有効に使おうとしているのである。free block のうち 2037 個は superblock が管理しており、この情報は fsworm にあるので失われない。しかし 2037 個を超えた部分の free block list は fscache の Tfree block に存在している。Tfree block は fsworm にコピーされない。これらは Recovery で失われる。

Other Configurations

2013/04/02

pseudo-RAID1

結局現在の cwfs configuration

filsys main c(/dev/sdC0/fscache)(/dev/sdC0/fsworm)

の下では fsworm の backup を取るのは至難の技であると諦めて、他の configuration

filsys main c(/dev/sdC0/fscache){(/dev/sdC0/fsworm)(/dev/sdD0/fsworm)}

を採用することとした。
これは pseudo-RAID1 の configuration である。デバイスまるごとではなく、fsworm partition だけを RAID1 風に処理してくれる。
/dev/sdC0/fsworm と /dev/sdD0/fsworm はサイズが異なっても構わない。その場合には小さい方に合わせられる。
書き込みの順序は、(この場合には) D0 → C0 であり、読み取りは C0 で行われる。

ディスク編成の変更にあたっては、準備が必要である。

コピーを取らなくてはならない。partition まるごとは時間がかかりすぎるので、最後の super block までのコピーに制限する必要がある。
それでもまだ時間が掛かりすぎるかも知れないので、その間の auto dump を止める必要がある。そのためには、cwfs にパッチをあてないといけない。

もっとも、RAID は僕が家庭で使うには大げさなのであるが...

家で使っている限り順調に動いている。大学のサーバーもこれでやることにした。

fake WORM

Cinap によると fake WORM の中には written block の bit map があるそうである。この場合、HDD を WORM の代わりに使うのだから、現在の利用状態を示す bit map を持つ事は可能なのである。この場合の configuration は

filsys main c(/dev/sdC0/fscache)f(/dev/sdC0/fsworm)

となる。

これを使えば、普段は 1 個の disk を使い、気の向いた時に backup disk を追加してバックアップを取る僕のような気まぐれな人間に適した処理が可能であろうと思える。

fake WORM の作成

僕の WORM は通常の WORM なので、fake WORM を作る場合には、device のコピーという訳には行かないはずてある。新たに構成する事とし、安全のために、PXE で立ち上げた端末で作業することとした。local disk には、これから cached fake WORM を構成する plan9 partition を準備しておく。

/dev/sdC0/fscache
/dev/sdC0/fsworm

この下で

cwfs64x -c -f /dev/sdC0/fscache

を実行する^注1。

注1: cwfs のコマンドの使い方は、Bell-labs 版(Geoff のオリジナル版)と 9front 版では異なる。ここでは 9front 版に基づく。9front 版では、kfs や fossil など、他のファイルシステムと -f オプションの使い方の統一を計っている。

9front 版では -c option で config mode に入る。config の prompt に対して次のデータを input する。

service cwfs
filsys main c(/dev/sdC0/fscache)f(/dev/sdC0/fsworm)
filsys dump o
filsys other (/dev/sdC0/other)
ream other
ream main
end

以上は一回限りである。

次に cwfs console へのコマンドと shell レベルのコマンドが発生する。ここでは cwfs console へのコマンドを fscons> で表す。

以下の操作は新しい window の中で行うのが無難である。

fscons> users default
fscons> newuser arisawa
fscons> allow

term% mount -c /srv/cwfs /n/cwfs
term% mkdir /n/cwfs/adm
term% cp /adm/users /n/cwfs/adm

fscons>	users

注意: newuser arisawa は、筆者のシステムの system owner は glenda ではなく arisawa だから必要になったのであり、glenda のままであれば不要である。

このあとは、筆者の cpdir を使うのが早い。

cpdir -mvug /root /n/cwfs adm 386 acme cfg cron lib mail rc sys

/root の下にある fd、mnt、n、tmp、usr は個別に確認した方が無難である。
特に、/root/n/ の下には cwfs が見えているはずである。

Tvirgo

fakeworm の場合には cwfs console の statw で表示される wsize から、Tvirgo block が始まる。Tvirgo block は fsworm の block 0 から wsize までの使用状況を bitmap で表している。書き込まれた block には bit 1 が立てられ、まだ書き込まれていない block の bit は 0 である。fsworm の先頭 2 block は書き込まれていないので、bitmap の最初の 2 bit は 0 である。

fakeworm は fsworm の末尾に bitmap が入り込むので、その分、wsize は小さくなる。

Misc.

What did I do that day?

2013/03/18

「あの日は何をしていたのだろう?」と僕が考える場合には、ファイルの修正などの話であり、飲みに行ったとかの話ではない。
あの日に変更されたファイルを全て列挙するには、UNIX では find コマンドを使うと思う。膨大なファイルの中から、変更されたファイルを探し出す作業は(ファイルの量にもよるが)多くの時間を要し数秒では終わらない。ちなみに僕の MacBook では僕の $HOME の探索だけでも30秒程要している。(結構たくさんのファイルを持っているせいもある)

bash$ touch a.txt
bash$ time find $HOME -newer a.txt -print
find: /Users/arisawa/.emacs.d/auto-save-list: Permission denied
/Users/arisawa/Library/Application Support/Google/Chrome/Default/Cookies
...
...
find: /Users/arisawa/src/rminnich-vx32-17a064eed9c2/src/9vx/osx/9vx.app: Permission denied

real	0m28.372s
user	0m0.783s
sys	0m18.783s
bash$

ここで紹介するのは僕の作った lr コマンドであり、find の -newer オプションに相当するオプションが存在する。これを使って昨日に変更されたファイルをサーバーの全てのファイルの中から見つけるには次のようにする。

term% cpu -h ar
ar% 9fs dump
mounting as arisawa
mounting as arisawa
ar% ls /n/dump/2013|tail -2
/n/dump/2013/0317
/n/dump/2013/0318
ar% mtime /n/dump/2013/0317
 1363498134 /n/dump/2013/0317
ar% time lr -lt 1363498134 /n/dump/2013/0318
...
...
--rw-rw-rw- web arisawa  5819730 2013/03/18 12:54:03 /n/dump/2013/0318/usr/cpa/www/log/dict
d-rwxrwxrwx arisawa arisawa        0 2013/03/17 21:51:56 /n/dump/2013/0318/usr/cpa/www/users
...
...
0.01u 0.18s 1.91r 	 lr -lt 1363498134 /n/dump/2013/0318
ar%

この日には33個のファイルの変更があった。多くは log ファイルである。変更されたファイルの中には web の cgi に拠るものもある。システムの全てのファイルを探しているのだが2秒弱で探索が完了している。僕は膨大なファイルをサーバー上に持っているにも係わらずである!

なぜこんなに高速に変更を調べられるのか?

探索に atime が利用されているからである。atime とは access time の意味である。マニュアルを見てもそれ以上に詳しい説明はない。(Plan9 のマニュアルには read time と書いてあるが、write に対しても atime が更新される)

注: lr は

http://plan9.aichi-u.ac.jp/netlib/cmd/lr/

に置かれている。

atime

2013/06/06

実際の動作を見ていると、Plan9 と UNIX(MacOSX や Linux) で振る舞いが異なる。

Plan9 の場合には、ファイルサーバがファイルを探し出すために辿ったルートに存在する全てのディレクトリの atime が更新されている。膨大な directory tree の中で、指定された日に実際にファイルサーバが辿った道は極く極く僅かである。従って atime を見ていれば、必要な探索のルートを大幅に減らす事が可能である。

UNIX では違う。ファイルサーバがファイルを探し出すために辿ったルートに存在するディレクトリの atime は更新されていない。変更が実際に発生したディレクトリやファイルの atime だけが更新されている。従って、atime を頼りに、更新を効率的に探し出す事はできない。

以下に、Plan9 と UNIX の atime の違いを具体例で示す。

Plan9

# Plan9
term% date; touch $home/doc/x;ls -dlu /usr $home/doc
Wed Jun  5 07:58:17 JST 2013
d-rwxrwxr-x M 20 sys     sys     0 Jun  5 07:58 /usr
d-rwxrwxr-x M 20 arisawa arisawa 0 Jun  5 07:58 /usr/arisawa/doc
term%

Linux

# UNIX (Linux)
hebe$ date; touch $HOME/doc/x; ls -dlu /home $HOME/doc
Wed Jun  5 07:56:41 JST 2013
drwxr-xr-x 3 root    root    4096 Jun  4 09:49 /home
drwxr-xr-x 9 arisawa arisawa 4096 Jun  5 07:46 /home/arisawa/doc
hebe$

OSX

# UNIX (OSX)
-bash$ date; touch $HOME/doc/x; ls -dlu /Users $HOME/doc
Wed Jun  5 08:08:27 JST 2013
drwxr-xr-x  6 root     admin  204 May 31 07:51 /Users
drwxr-xr-x  3 arisawa  staff  102 Jun  5 08:03 /Users/arisawa/doc
-bash$

cwstudy

この節は未完成である。

usage

cwstudy block_address

cwstudy -C block_address

cwstudy path

cwstudy super

文献

[cite:quinlan>] Sean Quinlan “A Cached WORM File System”
Softw., Pract. Exper., vol. 21 (1991), pp. 1289-1299
http://plan9.bell-labs.com/who/seanq/cw.pdf

[cite:collyer>] Ken Thompson, Geoff Collyer “The 64-bit Standalone Plan 9 File Server”
http://plan9.bell-labs.com/sys/doc/fs/fs.pdf