💾 Archived View for kamalatta.ddnss.de › cwfs-eng.txt captured on 2021-12-05 at 23:47:19.

View Raw

More Information

⬅️ Previous capture (2021-11-30)

➡️ Next capture (2024-07-08)

-=-=-=-=-=-=-

cwfs の研究 Study of cwfs

目次 table of contents

• 1.0.0 cwfs とは 1.0.0 What is cwfs
• 2.0.0 cwfs console 2.0.0 cwfs console
• 2.1.0 概要 2.1.0 Overview
• 2.2.0 fsworm のバックアップ 2.2.0 backup of fsworm
• 3.0.0 fsworm の構造 3.0.0 Structure of fsworm
• 3.1.0 Block 3.1.0 Block
• 3.2.0 dump stack 3.2.0 dump stack
• 3.3.0 Super Block 3.3.0 Super Block
• 3.4.0 Directory Entry Block 3.4.0 Directory Entry Block
• 3.5.0 Indirect Block 3.5.0 Indirect Block
• 3.6.0 File Block 3.6.0 File Block
• 3.7.0 Fsworm Root 3.7.0 Fsworm Root
• 3.8.0 ダンプの順序 3.8.0 Dump order
• 3.9.0 qid 3.9.0 qid
• 4.0.0 fscache の構造 4.0.0 Structure of fscache
• 4.1.0 Config Block 4.1.0 Config Block
• 4.2.0 Tcache Block 4.2.0 Tcache Block
• 4.3.0 Mapping 4.3.0 Mapping
• 4.3.1 bucket 4.3.1 bucket
• 4.3.2 cache entry 4.3.2 cache entry
• 4.3.3 age 4.3.3 age
• 4.3.4 state 4.3.4 state
• 4.4.0 free block and dirty block 4.4.0 free block and dirty block
• 4.5.0 msize と csize 4.5.0 msize and csize
• 4.6.0 Map from Worm to Cache 4.6.0 Map from Worm to Cache
• 4.7.0 msize の決定アルゴリズム 4.7.0 msize determination algorithm
• 4.8.0 Fscache Root 4.8.0 Fscache Root
• 5.0.0 Recovery 5.0.0 Recovery
• 5.1.0 復元 (recovery) 5.1.0 recovery
• 5.2.0 復元(recovery)について吟味 5.2.0 Review on recovery
• 5.3.0 Recovery によって失われるもの 5.3.0 What is lost by Recovery
• 6.0.0 Other Configurations 6.0.0 Other Configurations
• 6.1.0 pseudo-RAID1 6.1.0 pseudo-RAID 1
• 6.2.0 fake WORM 6.2.0 fake WORM
• 6.2.1 fake WORM の作成 6.2.1 Creating fake WORM
• 6.3.0 Tvirgo 6.3.0 Tvirgo
• 7.0.0 Misc. 7.0.0 Misc.
• 7.1.0 What did I do that day? 7.1.0 What did I do that day?
• 7.2.0 atime 7.2.0 atime
• 7.2.1 Plan9 7.2.1 Plan 9
• 7.2.2 Linux 7.2.2 Linux
• 7.2.3 OSX 7.2.3 OSX
• 8.0.0 cwstudy 8.0.0 cwstudy
• 8.1.0 usage 8.1.0 usage
• 9.0.0 文献 References

2012/10/20 2012/10/20
2013/03/14 更新 2013/03/14 renewal
2013/03/28 更新 Updated on March 20, 2013
2013/04/02 更新 Updated 2013/04/02
2013/04/10 更新 Updated 2013/04/10
2013/04/24 更新 2013/04/24 Update

2012年の夏休みは、9front の cwfs を試していた。 For the summer vacation in 2012, I
was trying 9front's cwfs. cwfs は fscache と fsworm で構成されているが、fsworm
の方から調べることとした。 cwfs consists of fscache and fsworm, but we decided to
look it up from fsworm. fsworm の方に関心がある理由は、ファイルの履歴等の情報は fsworm に置かれ、また
fscache がクラッシュした時のリカバリーも fsworm に基づいて行われるからである。 The reason why you are
more interested in fsworm is that information such as file history is
placed in fsworm and recovery when fscache crashes is done based on
fsworm.
もちろん、いかなるデバイスもやがては死を迎える。 Of course, any device eventually will die.
fsworm に対してもバックアップが必要である。 Backup is necessary for fsworm. cwfs 自体を
RAID に置くことも考えられようが、僕には大げさすぎる。 It may be possible to put cwfs itself in
RAID, but it's too overkill for me. もう一つ HDD を追加して、そこに fsworm
のコピーを持ちたい。 Add another HDD and want to have a copy of fsworm there.
それでは、どのようにコピーすれば、短時間でやれるのか? この問題を解明したかったのである。 So, how can we copy it
in a short time? I wanted to elucidate this problem.

9front 付属の cwfs は cwfs64x である。 The cwfs attached to 9front is cwfs64x.
そこで、ここでは cwfs64x に基づいて解説する。 Therefore, we will explain it based on
cwfs64x.

=======

注意: この記事は今のところ筆者のメモに過ぎない。 Note: This article is just my memo so far.
もちろん、誤りを含んでいるかも知れない。 Of course, it may contain errors.
誤りを発見したら知らせていただければ幸いである。 I would be pleased if you let me know if you
find an error.
=======

cwfs とは What is cwfs

この節は未完成である。 This section is incomplete. 暇な時に書く事とする。 I will write it in
my spare time.

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
図1. layer Figure 1. layer

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

Mac/OSX の time machine との比較 Comparison with Mac / OSX time machine
pdumpfs pdumpfs

以前はサーバのために1台を割り当てていた。 Previously we had one assigned for the server.
memory: ファイルサーバ専用機の中のメモリー memory: Memory in the dedicated file server
disk: disk cache disk: disk cache
WORM: 光ディスク WORM: Optical disc

現在は Plan9 の基で動くユーザープログラム cwfs Currently it runs under Plan 9 user
program cwfs
ユーザプログラムである事の利点: 仕組みを調べやすい。 Advantages of being a user program: It is
easy to check the mechanism.
memory: cwfs daemon 中のメモリー memory: memory in cwfs daemon
disk: ファイルサーバの fscache パーティション disk: fscache partition of file server
WORM: ファイルサーバの fsworm パーティション WORM: File server fsworm partition

cwfs (or cwfs32) cwfs (or cwfs32)
cwfs64 cwfs64
cwfs64x cwfs64x

cwfs console cwfs console

概要 Overview

cwfs に関する僕のパーティションのサイズは次の通りである。 The size of my partition on cwfs is as
follows.

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

cwfs コンソールはコマンド The cwfs console uses commands

con -C /srv/cwfs.cmd con -C /srv/cwfs.cmd

で使えるようになる。 You will be able to use with.

=======

注意: ウィンドを新たに1つ作って Note: Create one new window

cat /srv/cwfs.cmd cat /srv/cwfs.cmd

を実行しておいて、他のウィンドウから Run it from another window

echo statw>> /srv/cwfs.cmd echo statw>> /srv/cwfs.cmd

を実行してもよい。 May be executed. 配布版はこの方法を想定していると思われる。 Distribution seems to
assume this method.
=======

cwfs コンソールで statw を実行すると、fsworm の利用統計が出力される。 Running statw on the cwfs
console will output usage statistics for fsworm.次にその出力例を示す。 Next, an
example of the output is shown.

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

図2. cwfs コンソールでの statw の出力例。 Figure 2. Example of statw output from
the cwfs console.
プロンプト “> ” は、オフィシャルな配布版では出ない。 The prompt">" is not issued in the
official distribution version.
筆者による修正版で出るようにしている。 I am trying to go out with a modified version by
the author.

maddr から wsize までの、等号の右の数字(1列目と2列目)は、サイズを表している。 The numbers on the
right of the equal sign ( maddr to wsize) (the first and second
columns) represent the size. 1列目の数字の情報は、fscache の Tcache block (block
address 2) から得られる。 The information of the number in the first column
is obtained from Tcache block (block address 2) of Tcache. 2列目は fsworm
から得られる 注1 。 The second column is obtained from fsworm Note 1. これらの単位は
msize を除けば block である。 These units are block except for msize. msize
だけは bucket 数である。 Only msize is a bucket number.

注1: この部分は正しくない。 Note 1: This part is incorrect. 2列目も fscache から得られている。
The second row is also obtained from fscache. fsworm の最後の super block
の cache が fscache の中に含まれ、これを表示している。 The cache of the last super block
of fsworm is included in fscache and this is displayed. fsize
を除いて、2列目の情報は、最後の super block から得られる情報と一致している。 fsize for fsize, the
information in the second column matches the information obtained from
the last super block. fsize は statw コマンドを実行した時点での値であり、これは fscache の
Tcache block から得られる fsize と一致している。 fsize is the value at the time of
executing the statw command, which is consistent with fsize obtained
from the Tcache block of Tcache. (2013/04/24) (2013/04/24)

fsworm には、fsworm のパーティションサイズに関する情報は含まれない事に注目しよう。 Notice that fsworm
does not include information on fsworm's partition size. fsworm
が満杯になった時に、もっと大きなパーティションに置き換えられる可能性があるので、その場合には、単に満杯になったパーティションの内容を新しいパーティションにコピーすればよいように設計されているのであろう。
It may be replaced by a larger partition when fsworm is full, so in
that case it would be designed to just copy the contents of the full
partition to the new partition.

fscache も fsworm も block を単位として管理されている 注2 。 Both fscache and fsworm
are managed in block units. cwfs64x の場合には 1 block は 16KB である。 In the
case of cwfs64x, 1 block is 16 KB. 以下、block をアドレスで表すこととする。
Hereinafter, block is represented by an address. ba[0] は最初の block を
ba[1] は第2 block を意味する。 ba[0] means the first block, and ba[1] means
the second block.

wsize の 6972701 は /dev/sdC0/fsworm の大きさを block 数で表している。 wsize 6972701
/dev/sdC0/fsworm the size of /dev/sdC0/fsworm the number of blocks.

6972701*16*1024 == 114240733184 6972701 * 16 * 1024 == 114240733184

これは実際の /dev/sdC0/fsworm の大きさ 114240734208 よりも 1024 だけ少ないが、block
を単位として使用されている為に、使用できない領域が発生したのである。 This is 1024 less than the actual
size of /dev/sdC0/fsworm, but since it is being used as a unit, an
unusable area has occurred.

fsworm にはフォーマットの概念が存在しない事に注意すべきである。 It should be noted that there is
no concept of format in fsworm. なぜなら Write Once
だから、フォーマットしたらデータを書き込めない! 注3 Because it is Write Once, after formatting
it can not write data! 3

fsworm には先頭 block から順に書き込まれる。 It is written to fsworm in order from
the top block. snext (next super block) は、次に書き込まれる block を示している。 snext
(next super block) indicates the next block to be written. dump
を行うと、最初に super block と呼ばれる block が書き込まれ、それに続いてデータの本体が書き込まれる。 When you
dump, a block called super block is written first, followed by the
body of the data. Super block は、dump 毎の境界として、fsworm
においては基本的な役割を果たしている。 Super block serves as a boundary for every dump
and plays a fundamental role in fsworm.

sbaddr (super block address) は、最後に書き込んだ super block のアドレスである。 sbaddr
(super block address) is the address of the super block written last.
また、 slast は、その1つ前の super block のアドレスである。 Also, slast is the address of
the preceding super block.

注2: cwfs が管理する block は、ドライバが管理する読み書き単位としてのブロックとは別のものである。 Note 2: The
block managed by cwfs is different from the block as the unit of
reading / writing managed by the driver.
注3:最近では本来の意味での WORM を使う事はないであろう。 Note 3: WORM in its original meaning
will not be used recently. バックアップメディアとしての光ディスクの存在意義は無くなっており、ハードティスクで
WORM を代用する方が低コストで、かつ使い勝手も良い。 The significance of the existence of an
optical disk as a backup medium has disappeared, substituting WORM for
a hard task is low cost and easy to use. 以下の解説もハードディスクの使用を前提としている。 The
following explanation also assumes the use of a hard disk.

fsworm のバックアップ Backup of fsworm

2013/03/06 改訂 Revised 2013/03/06

fsworm は(その仕組み上)非常に堅牢ではあるが、それでもハードウェアクラッシュによるデータ消失のリスクを負っている。 Although
fsworm is very robust (in its mechanism), it still has the risk of
data loss due to hardware crashes. バックアップを行うには、fsworm のコピー(例えば
fsworm-bak)を持てばよい。 To do the backup you have a copy of fsworm (eg
fsworm-bak).

dump 毎に、fsworm の中に新たに生成された block
だけをコピーして行けばよいと考えるかも知れないが、話はそんなに簡単ではない。 For each dump, you might think
that you can copy only the newly created block in fsworm, but the
story is not that easy. なぜなら、書き込まれていない block が最後に dump された super block
の下に存在するからである。 This is because unwritten blocks exist under the last
dumped super block. 筆者の観察ではそれらには2種類ある。 In my observation there are two
kinds of them.
(a) reserved block 注1 (a) reserved blockNote 1
(b) free block (b) free block
である。.
(a)は、fscache の中で使用されているが、まだ dump が完了していない fsworm の block である。 (a) is a
block of fsworm that is used in fscache, but has not yet completed
dump.
(b)は、今後 fscache が使用可能な fsworm の block である。 (b) is a block of fsworm
that fscache can use in the future.

注1: “reserved block” は筆者が勝手に使っている用語である。 Note 1:"reserved block" is a
term that I am using arbitrarily. この用語は文献には存在しない。 This term does not
exist in the literature.

fsworm の構造 Structure of fsworm

Block Block

fscache も fsworm も block を単位として管理されている。 Both fscache and fsworm are
managed in units of block. cwfs64x の場合には 1 block は 16KB である。 In the
case of cwfs64x, 1 block is 16 KB. 以下、block をアドレスで表すこととする。
Hereinafter, block is represented by an address. ba[0] は最初の block を
ba[1] は第2プロックを意味する。 ba[0] means the first block and ba[1] means the
second block. 共に、先頭の 2 block は特殊である。 Together, the first two blocks
are special. block のアドレスは 8 B のデータで指定される。 The address of block is
specified by 8 B data. プログラムの中ではデータ型が Off で示されている。 In the program, the
data type is indicated by Off.

fscache の場合には、 ba[0] には config 情報が置かれている。 In the case of fscache,
ba[0] contains config information. ba[1] は使われていないようである。 ba[1] seems
not to be used.
fsworm の場合にも先頭の 2 block が使用されている気配はない。 In the case of fsworm, there is
no indication that the first 2 blocks are used.

どの block も Tag を持っている。 Each block has Tag. もっとも、全ての block
がフォーマットされているのではない 注1 。 However, not all the blocks are formatted.

Tag の大きさは、cwfs64x の場合には 12B であり、block の末尾に置かれる。 The size of Tag is 12
B in the case of cwfs 64 x, and it is placed at the end of the block.
その構造は次のようなものである。 Its structure is as follows.

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

pad の値は 0 である。 The value of pad is 0. tag が block の種類を表している。 tag
indicates the type of block. path の値に関する考え方は tag 毎に異なる。 path way of
thinking about the value of path is different for each tag.

16KB から Tag の 12B を除く領域がデータ領域(以下、Data で表す)であり、block の種類毎の構造を持っている。 The
area excluding Tag 12B is a data area (hereinafter referred to as
Data) from 16 KB and has a structure for each type of block. 纏めると To
summarize

block = Data + Tag block = Data + Tag

である。.

注1:最近の HD は容量が大きい。 Note 1: Recent HD has large capacity. もしも全ての block
をフォーマットすると膨大な時間を要する。 Formatting all the blocks takes a huge amount of
time. さらに言えば、WORM デバイスはフォーマットすれば書き込めなくなる! In addition, the WORM device
can not write if formatted!

dump stack dump stack

2013/02/28 2013/02/28

dump を繰り返すと、fsworm には、ダンプしたデータが積み重ねられる。 When dump is repeated, dumped
data is stacked on fsworm. データは決して上書きされることはない。 Data will never be
overwritten.その様子を図3(左)に示す。 The situation is shown in Fig. 3 (left).

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
図3. dump Figure 3. dump

以下、block address n の block を ba[n] で表す。 Hereinafter, the block of
block address n is represented by ba[n]. ba[0] と ba[1] は使われていない。 ba[0]
and ba[1] are not used. cwfs が実行されると、最初に 3 つの block When cwfs is
executed, first three blocks

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

が作られる。 Is made. この中には fscache の中に含まれるファイルの情報は含まれていない。 It does not
contain information on files included in fscache.
注意: “cfs root block” とか “dump root block”
とかの言葉は正式なドキュメントやプログラムコードの中には現れない。 Note: The words"cfs root block" or
"dump root block" do not appear in formal documents or program code.
“cfs root address” と “dump root address” は現れる。"Cfs root address" and
"dump root address" appear.

dump 毎に block が積み上げられる。 Blocks are stacked for each dump. 1回の dump
で積み上げられる block を単に dump と呼ぶ事にする。 We call the block that is stacked
with one dump simply as dump. 1つの dump の中には必ず3つの block, “super block”,
“cfs root block”, “dump root block” が含まれる。 One dump always includes
three blocks,"super block","cfs root block","dump root block".
図3(右)には、dump の内部構造が示されている。 Figure 3 (right) shows the internal
structure of dump.

super block と cfs root block の間の block には、fscache の内容が(前回の dump
から更新された差分だけ)保存される。 In the block between super block and cfs root
block, the content of fscache is saved (only the difference updated
from the previous dump).

cfs root block と dump root block の間の block には、dump された年月日の情報が含まれる。 The
block between the cfs root block and the dump root block contains
information on the dumped date. 必要な block 数は dump の回数に依存する。 The
required number of blocks depends on the number of dumps.

Super Block Super Block

fsworm の構造を捉える上で、もっとも基本的なのは super block である。 The most basic thing to
capture the structure of fsworm is super block. super block の tag は
Tsuper (=1) である。 The tag of super block is Tsuper (= 1). cwfs
のコードを読むと、super block の Tag の中の path は、 QPSUPER (=2) となっている。 When we
read the code of cwfs, the path the Tag of super block is QPSUPER (=
2).

super block は、fscache をダンプした時に 1 つ作られる。 One super block is created
when you dump fscache. まず super block が fsworm に書き込まれ、続いてデータの本体が block
単位に書き込まれる(図3右)。 First, super block is written to fsworm, then the body
of the data is written block by block (right in Figure 3).

super block の構造は The structure of super block

struct Superb struct Superb
{ {
Fbuf fbuf; Fbuf fbuf;
Super1; Super 1;
};};

を持つ。 have.

Fbuf は free block のアドレスの配列を内部に保有している。 Fbuf has an array of addresses
of free blocks inside. free block に関する解説は後回しにする。 I will postpone
commentary on free block.

Super1 が重要である。 Super1 is important.

struct Super1 struct Super 1
{ {
Off fstart; Off fstart;
Off fsize; Off fsize;
Off tfree; Off tfree;
Off qidgen; /* generator for unique ids */ Off qidgen; / * generator
for unique ids * /
/* / *

	
Stuff for WWC device * Stuff for WWC device
	
/ * /

Off cwraddr; /* cfs root addr */ Off cwraddr; / * cfs root addr * /
Off roraddr; /* dump root addr */ Off roraddr; / * dump root addr * /
Off last; /* last super block addr */ Off last; / * last super block
addr * /
Off next; /* next super block addr */ Off next; / * next super block
addr * /
};};

図4. Super1 の構造 Figure 4. Structure of Super1

ここで分かるように、各々の super block は、次の super block のアドレス( next)を保有している。 As can
be seen, each super block has the address ( next) of the next super
block.そして最初の super block は ba[2] から始まる。 And the first super block
starts with ba[2]. 従って ba[2] から順に super block
を辿れば、次にダンプされるアドレズが分かることになる。 Therefore, if you follow the super block
from ba[2] order, you will know the address to be dumped next.
次に、その出力結果例を示す。 Next, an example of the output result is shown.
(このツールは後に紹介する) (This tool will be introduced later)

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

最後の 1755393 は、次に作られる予定の super block アドレスである。 The last 1755393 is the
super block address to be made next. ba[1755217] の中の Super1
の内容は(例えば)次のようなものである。 The contents of Super1 ba[1755217] are (for
example) as follows.

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

これらの情報の一部は cwfs のコンソールからも得られる。 Some of these information is also
obtained from the cwfs console.

sbaddr 1755217: 現在の super block (最後に書き込まれた super block) sbaddr 1755217
: current super block (last written super block)
snext 1755393:次のダンプ予定のアドレス(つまり、次に作られる予定の super block アドレス) snext
1755393: The next dump schedule address (that is, the super block
address to be created next)
slast 1754642: sbaddr より一つ手前の super block アドレス slast 1754642: super
block address one before the sbaddr

Directory Entry Block Directory Entry Block

2013/03/02 更新 Updated 2013/03/02

次に基本的なのは directory entry block である。 Next is the directory entry block.
この block の Tag.tag は Tdir である。 Tag.tag of this block is Tdir. また、
Tag.path は、親ディレクトリの qid に一致する。 Also, Tag.path matches the Tag.path of
the parent directory.

directory entry block には次の directory entry ( Dentry) が1個以上(cwfs64x
の場合、最大62個)含まれている。 The directory entry block contains one or more of
the following directory entries (Dentry) (up to 62 in the case of
cwfs64x).

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

図5. Directory entry Figure 5. Directory entry

ここにはファイルやディレクトリの名前( name)が含まれているので、 Dentry のサイズは許容する名前の長さ( NAMELEN-1
)に依存する。 Since the names of files and directories are included here,
the size of NAMELEN-1 depends on the allowable name length ( NAMELEN-1
).

dump root block は directory entry block の 1 つである。 The dump root block
is one of directory entry blocks. 筆者の家庭でのシステムの場合には次のように dump した日付が見える。
In the case of my system at home, you can see the dumped date as
follows.

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

最初の行は初めて dump を行った時に(2012年8月1日)生成されている。 The first line is generated
for the first time on dump (August 1, 2012).

ls -l /n/dump/2012/0801 ls - l / n / dump / 2012/0801

を実行すると次のように、この日のファイルにアクセスできる。 You can access the files on this day as
follows.

maia% 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/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/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/68020
d-rwxrwxr-x M 495 sys sys 0 Jul 31 2012 /n/dump/2012/0801/acme
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 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 / 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 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 / 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 /
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 / 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 / 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 / sparc
64
d-rwxrwxr-x M 495 sys sys 0 Jul 31 2012 /n/dump/2012/0801/sys
d-rwxrwxr-x M 495 sys sys 0 Jul 31 2012 / n / dump / 2012/0801 / sys
dr-xr-xr-x M 495 sys sys 0 Jan 18 2012 /n/dump/2012/0801/tmp
dr-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
d-rwxrwxr-x M 495 sys sys 0 Aug 1 2012 / n / dump / 2012/0801 / usr
maia% maia%

図6. ls /n/dump Figure 6. ls / n / dump

dump した年月日情報 ( YYYY/MMDD) は dump root address と cfs root address
の間にある。 The dumped date information ( YYYY/MMDD) is between dump root
address and cfs root address. (図3) (Figure 3)

このケースでは次の図7に示すように block が繋がっている。 In this case, blocks are connected as
shown in the next figure 7.

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
図7. directory entry block の繋がり Figure 7. Connection of directory entry
block

長方形が1つのブロックを表している。 A rectangle represents one block. この図ではどれも
directory entry block である。 In this figure, none is a directory entry
block. dump の回数がまだ少ないので、2013年の月日の情報は1個の directory entry block
で間に合っているが、そのうちに複数の block が要求されるようになるだろう。 Since the number of dumps is
still small, the date information of 2013 can be made in time with one
directory entry block, but multiple blocks will be required within the
time.

Plan9 では図5の Dentry 構造体を見れば分かるように、directory の名前と、mode などの情報が同じ block
に同居している。 In Plan 9, as you can see from the Dentry structure in Figure
5, the name of directory and the information such as mode live in the
same block. 他方 UNIX では mode などの情報は、inode に置かれ、名前の一覧とは別の block
になっている(図8)。 On UNIX, on the other hand, information such as mode is
placed in the inode and is a block different from the list of names
(Fig. 8). この違いの起源は UNIX では hard link のサポートのために、link counter を名前とは別の
block (具体的には inode) に持たなくてはならないからだと思える。 The origin of this difference
seems to be that in UNIX, in order to support hard link, it is
necessary to have the link counter in another block (specifically,
inode) different from the name.

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
図8. unix inode の概念図で contents と書いたのは、file の中身であったり、他の directory
であったりする。 Figure 8. In the conceptual diagram of unix inode, we write
contents as contents of file or other directory.

Dentry の Qid9p1 構造体は Qid9p1's Qid9p1 structure

struct Qid9p1 struct Qid 9 p 1
{ {
Off path; /* was long */ Off path; / * was long * /
ulong version; /* should be Off */ ulong version; / * should be Off *
/
};};

であるが、この path は、 mode がディレクトリの場合(つまり mode&DDIR!= 0 の場合)には先頭ビットに 1
が立てられている。 However, this path is set to 1 in the first bit when mode is
a directory (that is, when mode&DDIR!= 0).
(このように設計した理由に関しては僕は今のところ解らない。) 正式な qid、すなわち、コマンド (I'm not sure about
the reason why I designed this way.) The official qid, ie the command

ls -ql ls - ql

で表示される qid は、この qid.path の先頭ビットを落としたもの、すなわち qid.path&~DDIR である。 The
qid displayed is the one with the first bit of this qid.path, that is,
qid.path&~DDIR.

cwfs64x の場合、1つの Dentry は 260 B である。 In the case of cwfs 64 x, one
Dentry is 260 B. 従って、1つの block には最大 62 個の Dentry を保持できる。 Therefore,
one block can hold up to 62 Dentry.

name には、ファイル名やディレクトリ名が入る。 name contains the file name and directory
name. NAMELEN は cwfs64x の場合には 144 である。 NAMELEN is 144 in the case of
cwfs NAMELEN x. 名前は'\0' で終わるので、名前の最大長は 143 文字である。 Since the name ends
with'\0', the maximum length of the name is 143 characters.
名前の他に、ディレクトリやファイルにとって基本的な情報がこの中に含まれている。 In addition to the name, basic
information for directories and files is included in this.

Dentry がファイルを表している場合( mode&DDIR == 0)、ファイルコンテンツの置かれている block は direct
block ( dblock[NDBLOCK]) と indirect block ( iblocks[NIBLOCK])
を基に辿る事ができる。 Dentry mode&DDIR == 0 represents a file ( mode&DDIR == 0),
the block dblock[NDBLOCK] the file contents can be traced based on
direct block ( dblock[NDBLOCK]) and indirect block ( iblocks[NIBLOCK]
). ファイルコンテンツを含む block は Tfile でタグ付けられている。 The block containing the
file contents is tagged with Tfile.

Dentry がディレクトリの場合( mode&DDIR!= 0
)には、そのディレクトリコンテンツ(中に含まれているファイルやディレクトリの情報)の置かれている block
は、ファイルの場合と同様に、direct block ( dblock[NDBLOCK]) と indirect block (
iblocks[NIBLOCK]) を基に辿る事ができる。 Dentry mode&DDIR!= 0 is a directory (
mode&DDIR!= 0), the mode&DDIR!= 0 in which the directory contents (the
information of the files and directories contained therein) is placed
is set to direct block ( dblock[NDBLOCK]) and indirect block (
iblocks[NIBLOCK]). ディレクトリコンテンツを含む block は Tdir でタグ付けられている。 The block
containing the directory contents is tagged with Tdir.

cwfs64x の場合には NDBLOCK の値は 6、 NIBLOCK の値は 4 である。 In the case of NDBLOCK
the value of NDBLOCK is 6 and the value of NIBLOCK is 4.

6 個の direct block には、データが直接書かれる。 Data is directly written to 6 direct
blocks. 1つの direct block には 16*1024 - 12 B のデータが書き込めるので、6 個の direct
block には合計 6*(16*1024 - 12) B のデータを書き込める。 Because 16 * 1024 - 12 B
data can be written in one direct block, 6 direct blocks can be
written with a total of 6 * (16 * 1024 - 12) B data. ディレクトリの場合には
372(=62*6)個までの Dentry が扱える事となる。 In the case of a directory, up to 372
(= 62 * 6) Dentry can be handled.

Indirect Block Indirect Block

directory entry block の Dentry 構造体に含まれる iblocks[0] によって示される block には、
For the block indicated by iblocks[0] included in the iblocks[0]
structure of the directory entry block,

(16*1024 - 12)/8 = 2046 (16 * 1024 - 12) / 8 = 2046

個の block アドレスが含まれる。 Block addresses. ここの 8 は 1 個の block アドレスの大きさである。
Here, 8 is the size of one block address.) これらの block アドレスは、データの場所(つまり
direct block)を示している。) These block addresses indicate the location of
the data (ie direct block). 従って Therefore

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

のデータを書き込める。 Can be written. このような block 情報を 1次の indirect block
と言うこととしよう。 Let's say that such block information is the primary
indirect block.

iblocks[1] には、2次の indirect block が書かれる。 iblocks[1], a secondary
indirect block is written. つまり、この block には block
アドレスが書かれているのであるが、それらのアドレスは(データの場所ではなく) 1次の indirect block アドレスである。 In
other words, the block addresses are written in this block, but these
addresses are the primary indirect block addresses (not the data
location). 従って Therefore

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

のデータを書き込める。 Can be written.

同様に、 iblocks[2] には Likewise, iblocks[2] has

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

そして iblocks[3] には And iblocks[3] has

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

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


となる。.

indirect block のタグは The tag of indirect block

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

となっている。. また、これらの Tag.path はどれも親ディレクトリの qid に一致する。 Also, any of these
Tag.paths matches the qid of the parent directory.

File Block File Block

ファイルの内容を含む block は Tfile のタグが付けられている。 The block containing the
contents of the file is tagged with Tfile. この block の Tag.path
は、このファイルが属するディレクトリの qid に一致する。 Tag.path of this block matches the qid
of the directory to which this file belongs.

1つの file block には、最大 One file block has a maximum

16*1024 - 12 B 16 * 1024 - 12 B

のファイルデータを保存できる。 File data can be saved.

ファイルの内容は block 単位で管理されている。 The contents of the file are managed in
block unit. ファイルの内容が更新された時には全ての block が書き換えられるのだろうか? 筆者の実験によると否である。
Will all blocks be rewritten when the contents of the file is updated?
According to my experiment, it is not.
1ブロックよりも大きなファイルの末尾にデータを追加すると、最後の block だけが更新される。 If you add data to
the end of a file larger than one block, only the last block is
updated. 他の block は、そのまま利用される。 Other blocks are used as they are.
もっとも、この実験は However, this experiment
(a) ファイルに append 属性を指定している (a) The append attribute is specified in
the file
(b) ファイルの末尾に seek して書き込んでいるのいずれかの条件の下で実験している。 (b) writing at the end
of the file by seeking at the end of the experiment under either
condition.

16KB を超える大きなファイルをテキストエディタで開いて、末尾にデータを追加した場合には、完全に書き換えられると思う。 If I open
a large file larger than 16 KB with a text editor and add data to the
end, I think that it can be completely rewritten. (実験はしていないけど...) (I
have not done an experiment though...)

書き換えられた block だけが新たに生成される cwfs の特性は、特にサーバで重要である。 Characteristics of
cwfs in which only rewritten blocks are newly generated is
particularly important in servers. 筆者のサーバではウェブのサーバのログファイルは 1.7GB にも上る。
On my server, the log file of web server is 1.7 GB.

1757143424 Oct 18 17:13 http 1757143424 Oct 18 17: 13 http

この大きさのファイルのコピーを毎日作り続けるわけには行かないであろう 注1 。 It will not go on to keep
copying files of this size every day1.

注1: Mac/OSX の TimeMachine や Linux の pdumpfs
では、ファイルが更新されていれば、そのコピーが新たに作られていく。 Note 1: On Mac / OSX's Time Machine
or Linux pdumpfs, if the file has been updated, a new copy of it will
be made. ハードリンクだけで TimeMachine の機能を実現しようとすれば、コピーは不可避な仕様になるはずである。 If we
try to realize the function of TimeMachine with only hard links, copy
will be inevitable specification.
サーバでは、日々更新される大きなログファイルを抱え込むので、サーバー用途には全く向かないはずである。 Since the server
carries a large log file which is updated day by day, it should not be
suitable for server use at all. データベースファイルの場合には、cwfs と言えども日々の dump
から外さなくてはならないだろう。 In the case of database files, even cwfs should be
removed from daily dump. トランザクションのログを採る方が安全である。 It is safer to log
transactions.

Fsworm Root Fsworm Root

2013/03/09 2013/03/09

fsworm の全ての情報は dump stack のトップにある dump root block から辿る事ができる。 All
information on fsworm can be traced from the dump root block at the
top of the dump stack. このアドレスは cwfs console の roaddr から知ることができる。 You
can find out this address from roaddr of cwfs console.
図6および図7は、ここから辿って見えるパスの最初の部分である。 Figures 6 and 7 are the first part of
the path seen from here.

実は roaddr は fscache が管理している root block であるが、fsworm の dump root block
と一致している。 Actually roaddr is a root block managed by fscache, but it
matches dump root block of fsworm.

ダンプの順序 Dump order

ダンプは現在の fscache に基づいて行われる。 The dump is done based on the current
fscache.そして、まず最初に super block が fsworm に書き込まれる。 First, super block is
written to fsworm. これに続いて、ディレクトリツリーの末端の情報から順に書き込まれる。 Following this,
the information at the end of the directory tree is written in order.
従って、fsworm の中に、例えば Thus, in fsworm, for example

/2012/0925/.... / 2012/0925 /....

が作成される場合には、一番最後に /、その前に 2012 、さらにその前に 0925 が... Is created, the last /
before 2012, before 0925 before that...

qid qid

ユーザからは ls command に q option を添えてファイルやディレクトリの qid を見ることができる。 From the
user, you can see the qid of the file or directory by adding q option
to ls command. 例えば For example

maia% ls -ql maia% ls - ql
(000000000009baa2 6 00) --rw-rw-r-- M 326 web web 33597 Mar 8 15:01
bucket.png (000000000009 baa2 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 (000000000009 baa 3 300) - 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 (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 (0000000000089b8d 2 00) - rw - rw - r - M 326 arisawa
web 2401 Oct 15 21:21 cwfs.svg
......
maia% maia%

のように表示される。 As shown in FIG. 先頭の () の中の 16 進数表示の部分が qid であり、その次の数字が qid
version である。 The part of hexadecimal notation in the head () is qid,
and the next digit is qid version.
マニュアルによると qid はfile system の中でユニークであると言う。 According to the manual qid
is unique within the file system.

ユニークであるならば、qid が管理されなくてはならない。 If it is unique, the qid must be
managed. super block の中の qidgen が、そのためにあると思える(図4)。 It seems that
qidgen in super block is there for that (Figure 4).

実験をして見れば分かるが qid はファイル名の変更によっては変わらない。 You can tell by experimenting
but qid does not change by changing file name. 内容が変わると version が変わる。
Version changes when content changes.
そうであるから、エディタを作る場合には、保存時に他の何かによって変更を受けたか否かを知るために使えるのであるが、time stamp
の方が手軽なので僕はこれまでに qid を利用した事は無い。 So, when creating an editor, you can
use it to know whether or not you have changed by something else at
the time of saving, but time stamp is easier, so I used qid so far
There is nothing. (なお unix の qid は、違うものらしい) (The qid of unix seems to
be different)

fsworm や fscache の中を除くと、qid とその version は directory entry
の中に含まれ(図5)、その contents に関する block が同じ qid となっていることが分かる。 Except in
fsworm and fscache, qid and its version are included in the directory
entry (Figure 5), and you can see that the block concerning the
contents is the same qid. つまり block の所属を確認するために使われていると思われる。 That is,
it seems to be used to confirm the affiliation of block.

fscache の構造 Structure of fscache

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

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

Config Block Config Block

2013/03/05 2013/03/05

cwfs64x を見る限り、筆者の config block ( ba[0])
には、テキスト形式で次のようなデータが先頭から書き込まれていた。 As far as cwfs64x is concerned, the
following data was written in the text format from the beginning in my
config block ( ba[0]). (この内容は cwfs console の printconf コマンドでも見える)
(This content can also be seen with the printconf command of cwfs
console)

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

=======

noauth は、認証をしないで cwfs へのアクセスを許す事を意味している。 noauth means allowing access
to cwfs without authentication. noauth
は安全な環境での実験レベルでしか許されない特殊な設定である事に注意すべきである。 noauth should be noted that
noauth is a special setting only allowed at the experimental level in
a secure environment.
大学で使っているのは、今年の2月の版であり、これは noauth にはなっていない。 What I use at university is
the February version of this year, which is not noauth. (2013/04/10)
(2013/04/10)
=======

さらに、この block は次のように tag 付けられている。 In addition, this block is tagged as
follows.

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

ソースコードには、次の構造化データがある。 The source code has the following structured
data.

struct Conf struct Conf
{ {
ulong nmach; /* processors */ ulong nmach; / * processors * /
ulong nuid; /* distinct uids */ ulong nuid; / * distinct uids * /
ulong nserve; /* server processes */ ulong nserve; / * server
processes * /
ulong nfile; /* number of fid -- system wide */ ulong nfile; / *
number of fid - system wide * /
ulong nwpath; /* number of active paths, derived from nfile */ ulong
nwpath; / * number of active paths, derived from nfile * /
ulong gidspace; /* space for gid names -- derived from nuid */ ulong
gidspace; / * space for gid names - derived from nuid * /
ulong nlgmsg; /* number of large message buffers */ ulong nlgmsg; / *
number of large message buffers * /
ulong nsmmsg; /* number of small message buffers */ ulong nsmmsg; / *
number of small message buffers * /
Off recovcw; /* recover addresses */ Off recovcw; / * recover
addresses * /
Off recovro; Off recovro;
Off firstsb; Off firstsb;
Off recovsb; Off recovsb;
ulong configfirst; /* configure before starting normal operation */
ulong configfirst; / * configure before starting normal operation * /
char *confdev; char * confdev;
char *devmap; /* name of config->file device mapping file */ char *
devmap; / * name of config-> file device mapping file * /
uchar nodump; /* no periodic dumps */ uchar nodump; / * no periodic
dumps * /
uchar dumpreread; /* read and compare in dump copy */ uchar
dumpreread; / * read and compare in dump copy * /
uchar newcache; uchar newcache;
};};

この中のデータは、初期化過程の中で、cwfs の種類毎に(ソースコードの中で)与えられている。 Data in this is given
(in the source code) for each type of cwfs during the initialization
process.

Tcache Block Tcache Block

Tcache block は cwfs に関する基本情報を管理している。 Tcache block manages basic
information about cwfs. この内容は cwfs コンソールで見ることができる。 You can see this in
the cwfs console.

struct Cache struct Cache
{ {
Off maddr; /* cache map addr */ Off maddr; / * cache map addr * /
Off msize; /* cache map size in buckets */ Off msize; / * cache map
size in buckets * /
Off caddr; /* cache addr */ Off caddr; / * cache addr * /
Off csize; /* cache size */ Off csize; / * cache size * /
Off fsize; /* current size of worm */ Off fsize; / * current size of
worm * /
Off wsize; /* max size of the worm */ Off wsize; / * max size of the
worm * /
Off wmax; /* highwater write */ Off wmax; / * highwater write * /
Off sbaddr; /* super block addr */ Off sbaddr; / * super block addr *
/
Off cwraddr; /* cw root addr */ Off cwraddr; / * cw root addr * /
Off roraddr; /* dump root addr */ Off roraddr; / * dump root addr * /
Timet toytime; /* somewhere convienent */ Timet toytime; / * somewhere
convienent * /
Timet time; Timet time;
};};

fscache の各ブロックはメモリーにキャッシュされている。 Each block of fscache is cached in
memory. 10秒毎にメモリーのキャッシュは、(更新があれば) fscache に書き込まれる。 Every ten seconds
the cache of memory is written to fscache (if there is an update).

Mapping Mapping

2013/03/08 更新 Updated 2013/03/08

fsworm の各 block は、図9の cache area の cache block に mapping される。 Each
block of fsworm is mapped to the cache block of the cache area of
​​FIG.

fscache の cache block のアドレスを cba とすると cba は Let cba be the cache block
address of cba, cba

caddr <= cba < caddr + csize caddr <= cba <caddr + csize

の範囲にある。. fsworm の 0 から wsize の block が fscache のこの領域に map される。 A block
of fsworm 0 to wsize is mapped to this area of ​​fscache.

cache block の総数は(cwfs コンソールでは) csize で表示されている。 The total number of
cache blocks is indicated by csize (in the cwfs console). caddr
から始まる、残りの全ての block が cache block ではない事に注意する。 caddr all remaining caddr
starting with caddr are not cache blocks.

筆者のシステムの例では fsworm の block 数は 6972701 であるのに対して、fscache の cache block
数は 1392255 である。 In the example of my system, the number of blocks of
fsworm is 6972701, whereas the number of cache blocks of fscache is
1392255. 従って 1/5 程度のキャッシュ能力を持っている。 Therefore, it has about 1/5 cache
capacity. また、fscache には 1394540 個の block
が採れるが、実際に使われているのは、1035+1392255(=1393290) に過ぎない。 Also, 13604540 blocks
can be taken in fscache, but only 1035 + 1392255 (= 1393290) are
actually used. 未使用領域は 0.1% 程度である。 The unused area is about 0.1%.

単純に考えると表1に示すような mapping を思い浮かべるかも知れない。 Just thinking about it might
think of mapping as shown in Table 1.

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
表1. a simple but problematic mapping from fsworm to cache Table 1. a
simple but problematic mapping from fsworm to cache

ここに、cache と書いたのは fscache の cache area である。 Here, cache is written in
fscache's cache area.示されている address は caddr から数えている。 The address shown
is counted from caddr.

しかし、この mapping は問題を孕んでいる。 However, this mapping suffers from problems.
ある fsworm block が cache されていると、同じ cache block に map される他の fsworm block
が cache に入り込めない場合がある。 If an fsworm block is cached, there may be cases
where other fsworm blocks that are mapped to the same cache block can
not enter cache.

そこで cwfs では、間に bucket をかませて、mapping に柔軟性を持たせている。 So cwfs keeps bucket
in between, giving flexibility to mapping.その様子を表2に示す。 The situation is
shown in Table 2.

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
表2. real mapping implementation of cwfs. Table 2. real mapping
implementation of cwfs.

説明を容易にするために fsworm の block address を wa とし、 caddr から数えた cache の
address を ca とする。 For ease of explanation, block address of fsworm is
set to wa and cache address counted from caddr to ca wa%msize が同一の wa
は ca%msize の ca のどれかに map されると考えるのである。 wa%msize that wa%msize with the
same wa%msize is ca%msize to ca of ca%msize. 実際の mapping の状態は fscache
の map block にある bucket によって管理されている。 The state of actual mapping is
managed by bucket in map block of fscache.

bucket bucket

fscache の maddr から caddr までの block は map block で、その tag は Tbuck である。 A
block from caddr to caddr in maddr is a map block, and its tag is
Tbuck. map block は bucket の集まりで、bucket には cache の状態と、対応する fsworm の
block address が含まれている。 The map block is a collection of buckets, and
the bucket contains the state of cache and the block address of the
corresponding fsworm.

各 bucket は次の構造を持っている。 Each bucket has the following structure.

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

各 map block は最大 BKPERBLK (=10) 個の bucket を保有できる。 Each map block can
hold up to BKPERBLK (= 10) BKPERBLK.

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
図9. fscache の構造 (cwfs64x) Figure 9. Structure of fscache (cwfs64x)

fscache に含まれる bucket の総数は msize で与えられている。 The total number of msize
included in msize is given by msize. 以下、bucket に block address
の小さい方から順に 0 から msize - 1 までの番号を付け、それを bucket address と言う。 In the
following, bucket is numbered from 0 to msize - 1 in ascending order
of block address, and it is called bucket address.

cache entry cache entry

各 bucket は CEPERBK (=135) 個の Cache Entry を持っている。 Each bucket has
CEPERBK (= 135) Cache Entries. 各 Cache Entry は、現在のマップの状態を表している。 Each
Cache Entry represents the state of the current map.

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

fsworm の block address ba から、対応する fscache の block address cba
を見つけるには、まず In order to find the block address cba of the corresponding
fscache from the block address ba cba, first

bn = ba % msize bn = ba% msize

を計算する。.そして bucket[bn] の中の 135個の cache entry の waddr を調べる。 Then check
the waddr of 135 cache entries in bucket[bn]. もしも、fsworm の block
address ba の block が cache されていれば、その中に ba と一致するものが存在するはずである。 If the
block of block address ba of fsworm is cached, there should be some
matching ba it. この cache entry を entry[ce] とすると、 Letting this cache
entry be entry[ce]

cba = msize*ce+bn+caddr cba = msize * ce + bn + caddr

で求める事ができる。 Can be obtained with. 詳しくは「Map from Worm to Cache」で解説する。
Details are explained in"Map from Worm to Cache".

逆に、現在 cache されている fscache の block address cba から fsworm の block
address ba を求めるには、まず Conversely, to obtain the block address ba of cba
from the block address cba fscache currently being cached, first

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

を計算すれば bucket address bn が求まるので、その中の cache entry ce の waddr を見ればよい。
The bucket address bn can be found by looking up the waddr of the
cache entry ce in it.

fscache の cache area の block は cache entry によって「状態」を保有していることになる。 The
cache area block of fscache has"state" by cache entry. 以下、cache block
の状態は◯◯であるとか、cache block に対応する worm address は◯◯であるとか言う事にする。 In the
following, let's say that the state of the cache block is ◯◯ or the
worm address corresponding to the cache block is ◯◯.

age age

age は、cache block の古さを表している。 age represents the age of the cache
block. 小さい値が古い。 Small values ​​are old. だから概念的には age と言うよりも birth day
に近い。 So it is conceptually close to birth day rather than age. 新たに
cache する必要が発生した場合には、( Cnone が存在しない場合には) age の小さい cache が優先的に捨てられる。
When it becomes necessary to cache newly, the small cache of age is
preferentially discarded (when Cnone does not exist).そして bucket の
agegen の値が新たに割り当てる age の値となる。 And the value of agegen of bucket
becomes the value of age be newly allocated. cache にデータが割り当てられれば
agegen が 1 つ増加する。 If data is allocated to cache, agegen increases by
1. age の最大値 MAXAGE=10000 が存在する。 The maximum value MAXAGE=10000 age
exists.それを超えた時には、 age の再割当が必要になるはずであるが、詳細はコードをよく読んでいないのでわからない。 When it
exceeds it, reallocation of age is necessary, but details are not
understood because I have not read the code well.

state state

cache の state とは、対応する Centry の状態で、次の値を持つ。 The cache state is the state
of the corresponding Centry and has the following values.

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

cache されていない cache block の状態は Cnone になっている。 The state of an Cnone
cache block is Cnone to Cnone. 僕の観察では、この場合の waddr
はゴミであり意味を持っていないように思える。 In my observation, waddr in this case seems to
be garbage and has no meaning.

worm からデータを読み取った cache の場合には、 waddr は元の worm の addressそのものである。 In the
case of cache which reads data from worm, waddr is the address itself
of the original worm. cache の状態は Cread になっている。 The state of cache is
Cread. この場合には cache block の内容は対応する fsworm の block と同じである。 In this case
the contents of the cache block are the same as the corresponding
block of fsworm. (キャッシュであるから当然の事) (Naturally because it is a cache)

既存の directory や file が変更を受けると、その cache の Cread のタグが Cwrite に変化する。 When
an existing directory or file is changed, the Cread tag of that cache
changes to Cwrite.そして waddr は変更を受けない。 And waddr is not changed. もちろん
dump 時に上書きするわけには行かないのだから、その時には新しい worm address に保存され、同時に cache entry
の中の waddr も更新されるはずである。 Of course it will not go overwrite on dump, so
at that time it will be saved in the new worm address and waddr in the
cache entry should be updated at the same time. 異常なく dump されると状態は
Cread になるであろう。 If abnormally dumped, the state will be Cread.

新たに directory や file を作成した場合には、その cache block に対応する wba には worm の未使用の
address が割り当てられる。 When creating a new directory or file, wba
corresponding to that cache block is assigned an unused address of
worm. 状態は Cdirty になる。 The state is Cdirty. dump が完了すると Cread
になっているはずである。 When dump is completed it should be Cread.

状態 Cnone と Cread の cache は、 waddr に変更を反映させる必要は無い。 The cache of the
state Cnone and Cread does not need to reflect the change in waddr.
従って、この Centry に対応する fscache の block は(必要に応じて)捨てても構わないことを意味している。
Therefore, it means that the block of fscache corresponding to this
Centry may be discarded (if necessary).

ところで cwfs コンソールの statw コマンドを実行した時の By the way, when you run the cwfs
console statw command

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

では Centry を直接調べて、 state の値の分布(個数)を表示している。 We examine Centry directly
and display the distribution (number) of values ​​of state.

free block and dirty block free block and dirty block

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

次のように分類するのが良い。 It is better to classify as follows.
(a) unwritten block (a) unwritten block
(b) dirty block (b) dirty block
(c) free block (c) free block

(a) の unwritten block とは dumped area の中に存在する、未書き込みの block。 The
unwritten block in (a) is an unwritten block existing in the dumped
area.
(b) の dirty block とは fscache の中で Cdirty とされている block。 The dirty block
in (b) is a block which is called Cdirty in fscache. cwfs は、新たに file や
directory を作成する時に、cache に worm の address を対応付け、cache の block の状態を
Cdirty とする。 When cwfs creates a new file or directory, it associates
worm's address with cache, and Cdirty cache's state to Cdirty. この worm
address は未使用アドレスであり、unwritten block が使えるなら、それを使う。 This worm address is
an unused address, and if unwritten block is available, use it.
dump 直後には Immediately after dump

(a) ⊇ (b) (a) ⊇ (b)

である。.
(c) の free block とは dirty block のうち、fscache に free block として登録されている
block。 (c) free block is a block that is registered as a free block in
fscache among dirty blocks. これらは file tree に link されていない。 They are not
linked to the file tree. link されている dirty block は dump の対象となるが、link
から外れた block は dump されない。 Linked dirty blocks are subject to dump, but
blocks deviated from link are not dumped. 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
になっているはずである。(図10)

注意: あなたのブラウザは SVG をサポートしていません。 Note: Your browser does not support
SVG.最新のブラウザをお使いください。 Please use the latest browser.
図10. freelist chaine

msize と csize

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

csize = msize*CEPERBK

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

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

(msize+BKPERBLK-1)/BKPERBLK

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

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 個にした場合の可能な mn (= csize) の値は、

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

を満たす必要がある。 つまり、 In other words,

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

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

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

で得られる。 すなわち、 That is,

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

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

msize = (mn)/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% 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

この節は未完成である。 This section is incomplete.

usage

cwstudy block_address

cwstudy -C block_address

cwstudy path

cwstudy super

文献

[1] 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

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

1006