subversionのfsfsの内部構造を読んでみた

2015-09-09 by [e-mail]

subversionのバックエンドDBの一種の "fsfs" を、ダンプロードサイクルを回さずに直接編集することに取り組んでいる一環で、fsfsの「バージョン7の物理アドレスモード」の構造をほどいてみたのでメモしておく。
書きかけだし、間違ってる可能性もあるよ。

fsfsのディレクトリ構造

https://svn.apache.org/repos/asf/subversion/trunk/subversion/libsvn_fs_fs/structure を参考に。

• db/revs/1/123 に r123 の情報が入っている
• db/revprop/1/123 に r123の属性が格納されている
• db/current に最新リビジョン番号が書いてある
• db/tなんちゃら はコミット開始～終了の短い時間だけ使われる

くらいをおさえておけばよいかな。

revファイルの構造

https://svn.apache.org/repos/asf/subversion/trunk/subversion/libsvn_fs_fs/structure を参考に。
db/revs/1/123 といったようなファイルに、コミットの本体情報が入っている。
ファイルには、「データ領域」×N、「ノードリビジョン領域」×N、「変更パス情報」、そして末尾に「ルートノードのノードリビジョン領域の位置と変更パス情報の位置」が記載されている。

データ領域

PLAIN
K 7
SandBox
V 14
dir 0-5.0.r5/0
END
ENDREP

データ領域は、PLAINまたはDELTAから始まり、ENDREPで終わる。
PLAINで始まっているときは、{キー, 値} の組み合わせが K 長さ\n キー名\n V 長さ\n 値\n という表現で格納されている。例えばディレクトリノードでは、{ファイル名: 中身へのポインタ} が格納される。

DELTAで始まっているときは、svndiffフォーマットで格納されている。長くなるので後述する。

ノード情報領域

id: 0.0.r0/17
type: dir
count: 0
text: 0 0 4 4 2d2977d1c96f487abe4a1e202dd03b4e
cpath: /

key: value という形式で情報が書いてある。keyに指定できるのは、id, type, pred, count, text, props, cpath, copyfrom, copyroot, minfo-cnt, minfo-here であり、それ以外のキーは無視される。 ……ってことは適当なキーを指定してやればパディングに使えるね。

id値

idの構造は node_id '.' copy_id '.' txn_id である。
後続のリビジョンファイルからも参照されるので、むやみに名前を変えてはいけない!

• node_id は、そのノードリビジョンに順番に振られた番号([0-9][a-z]による36進数)
• copy_id は、新規アイテムのときは親ディレクトリと同じ、変更アイテムのときは新規に振られた番号
• txn_id は、rに続けてそのリビジョンの数字、スラッシュに続けて、そのノードリビジョン領域のオフセット値
• オフセット値とは、そのファイルの頭から何バイト目か、という意味。 vim で :set statusline=%o と指定してやって、カーソルをその id: の行頭に置いたときに表示される値。

変更パス情報領域

_0.0.t4-4 add-dir false false /SandBox

ルートノード位置、変更パス情報の位置

17 107

複数あるノードのうち、ルートノードとなるノードのオフセット位置と、変更パス情報領域のオフセット位置。vim で :set statusline=%o と指定してやって、カーソルを id: の行頭などに置いたときに表示される値。

svndiffの構造

https://svn.apache.org/repos/asf/subversion/trunk/notes/svndiff を参考に。
ソースとなるバイト列から、ターゲットとなるバイト列を生成するためのコマンドが格納されている。zlibで圧縮してみて短くなるようなら、コマンド列や新規データは圧縮される。

1. マジックナンバーとしての、SVN\0 または SVN\1
2. ソースの位置
3. ソースの長さ
4. ターゲットの長さ
5. コマンド列のバイト数
6. 新規データのバイト数
7. コマンド列の圧縮前のサイズ
8. コマンド列
9. 新規データの圧縮前のサイズ
10. 新規データ本体

コマンド列と新規データ本体以外は値が格納されている。値は可変長であり、最上位ビットは「後続あり」を意味する。つまり、 10000001 00000010 の場合は、 0b_0000001_0000010、つまり130を意味する。

コマンド

• 00xxxxxx nnnnnnnn: ソースデータの nnnnnnnn バイト目から xxxxxxバイトをコピー
• 01xxxxxx nnnnnnnn: ターゲットの nnnnnnnn バイト目から xxxxxxバイトをコピー
• 10xxxxxx: 新規データからxxxxxxバイトをコピー(新規データはxxxxxxバイト消化される)

svndiffのサンプル

ソースがaaaabbbbccccという文字列であるとき:

	01010011 01010110 01001110 00000000	Header ("SVN\0")

	00000000				Source view offset 0
	00001100				Source view length 12
	00010000				Target view length 16
	00000111				Instruction length 7
	00000001				New data length 1

	00000100 00000000			Source, len 4, offset 0
	00000100 00001000			Source, len 4, offset 8
	10000001				New, len 1
	01000111 00001000			Target, len 7, offset 8

	01100100				The new data: 'd'

ターゲットの長さは16バイト。

1. ソースの0バイト目から4バイト、つまり aaaa
2. ソースの8バイト目から4バイト、つまり cccc
3. 新規データから１バイト、つまり d
4. ターゲットの8バイト目から7バイト、つまり ddddddd

結果、 aaaaccccddddddddという文字列が生成される。

zlibの構造

zlibは、バイト列を圧縮するアルゴリズム。zlibだけではファイル名やタイムスタンプなどの情報は持たない。これら付帯情報をzlibの外側に持たせたりしたのがzipファイルだったりする。
http://tools.ietf.org/html/rfc1950 を参考に。読む。