エルドラド カジノ

JF Linux Kernel 3.x/2.6 Documentation: /usr/src/linux/Documentation/filesystems/logfs.txt


logfs ファイルシステムの解説 [プレインテキスト版]

Linux-3.3/Documentation/filesystems/logfs.txt の和訳です。
翻訳団体: JF プロジェクト <  >
更新日 : 2012/5/31
翻訳者 : Seiji Kaneko < skaneko at mbn dot or dot jp >

#The LogFS Flash Filesystem
LogFS フラッシュファイルシステム



#Two superblocks exist at the beginning and end of the filesystem.
#Each superblock is 256 Bytes large, with another 3840 Bytes reserved
#for future purposes, making a total of 4096 Bytes.
ファイルシステムの最初と最後に、各一つのスーパーブロック (合計 2 個)があり
ます。いずれも 256 バイトの長さで、将来の拡張のため 3840 バイトがリザーブさ
れているため、合わせて 4096 バイトになります。

#Superblock locations may differ for MTD and block devices.  On MTD the
#first non-bad block contains a superblock in the first 4096 Bytes and
#the last non-bad block contains a superblock in the last 4096 Bytes.
#On block devices, the first 4096 Bytes of the device contain the first
#superblock and the last aligned 4096 Byte-block contains the second
スーパーブロックの位置は、MTD とブロックデバイスで異なる可能性があります。
MTD の場合、最初の不良の無いブロックに最初の 4096 バイトのスーパーブロック
が、そして最後の不良の無いスーパーブロックに最後の 4096 バイト分が格納され
ます。ブロックデバイスでは、デバイスの最初の 4096 バイトに最初のスーパーブ
ロックが、そして最後のアラインされた 4096 バイトのブロックに二番目のスーパ

#For the most part, the superblocks can be considered read-only.  They
#are written only to correct errors detected within the superblocks,
#move the journal and change the filesystem parameters through tunefs.
#As a result, the superblock does not contain any fields that require
#constant updates, like the amount of free space, etc.
tunefs によるファイルシステムパラメータの変更時でのみ書き込まれます。この


#The space in the device is split up into equal-sized segments.
#Segments are the primary write unit of LogFS.  Within each segments,
#writes happen from front (low addresses) to back (high addresses.  If
#only a partial segment has been written, the segment number, the
#current position within and optionally a write buffer are stored in
#the journal.
LogFS での基本的な書き込み単位です。各セグメントでは、書き込みは最初 (低
位アドレス) から最後 (高位アドレス) の方向に向かって行われます。セグメン

#Segments are erased as a whole.  Therefore Garbage Collection may be
#required to completely free a segment before doing so.


#The journal contains all global information about the filesystem that
#is subject to frequent change.  At mount time, it has to be scanned
#for the most recent commit entry, which contains a list of pointers to
#all currently valid entries.

#Object Store

#All space except for the superblocks and journal is part of the object
#store.  Each segment contains a segment header and a number of
#objects, each consisting of the object header and the payload.
#Objects are either inodes, directory entries (dentries), file data
#blocks or indirect blocks.
inode か、ディレクトリエントリ (dentry) か、ファイルデータブロックか、間


#Garbage collection (GC) may fail if all data is written
#indiscriminately.  One requirement of GC is that data is separated
#roughly according to the distance between the tree root and the data.
#Effectively that means all file data is on level 0, indirect blocks
#are on levels 1, 2, 3 4 or 5 for 1x, 2x, 3x, 4x or 5x indirect blocks,
#respectively.  Inode file data is on level 6 for the inodes and 7-11
#for indirect blocks.
(GC) が失敗する可能性が出てきます。GC 動作の必要条件の一つは、データがツ
これは、実効的には、全てのファイルデータがレベル 0 にあった場合、1x, 2x,
3x, 4x, 5x の間接ブロックに対してレベル 1, 2, 3, 4, 5 の間接ブロックが順
に対応するということです。Inode ファイルデータは inode のレベル 6 に置か
れ、7-11 が間接ブロック向けになります。

#Each segment contains objects of a single level only.  As a result,
#each level requires its own separate segment to be open for writing.

#Inode File
Inode ファイル

#All inodes are stored in a special file, the inode file.  Single
#exception is the inode file's inode (master inode) which for obvious
#reasons is stored in the journal instead.  Instead of data blocks, the
#leaf nodes of the inode files are inodes.
inode は全て inode ファイルという特別のファイルに格納されます。ただ一つの
例外は、inode ファイルの inode (マスタ inode) で、これは理由はあきらかと
ファイルのリーフノードは inode になります。


#Writes in LogFS are done by means of a wandering tree.  A naïve
#implementation would require that for each write or a block, all
#parent blocks are written as well, since the block pointers have
#changed.  Such an implementation would not be very efficient.
LogFS への書き込みは、ツリーの探索によって行われます。素朴な実装だと一つ

#In LogFS, the block pointer changes are cached in the journal by means
#of alias entries.  Each alias consists of its logical address - inode
#number, block index, level and child number (index into block) - and
#the changed data.  Any 8-byte word can be changes in this manner.
LogFS では、ブロックポインタの更新はエイリアスエントリとしてジャーナルに
キャッシュされます。各エイリアスには論理アドレス (inode 番号、ブロックイ
ンデックス、レベルと子番号 (ブロックへのインデックス)) と、更新データが格
納されています。各 8 バイト (1 ワード) は、このような内容の変更である可能
<!-- TODO ? -->

#Currently aliases are used for block pointers, file size, file used
#bytes and the height of an inodes indirect tree.
inode の間接ツリーの深さデータの格納にエイリアスが用いられています。

#Segment Aliases

#Related to regular aliases, these are used to handle bad blocks.
#Initially, bad blocks are handled by moving the affected segment
#content to a spare segment and noting this move in the journal with a
#segment alias, a simple (to, from) tupel.  GC will later empty this
#segment and the alias can be removed again.  This is used on MTD only.
動され、移動したことがセグメントエイリアスとして、単純なタプル (移動元、
移動先) 形式でジャーナルに記録されます。そののち GC がこのセグメントを空
にし、エイリアスは再度削除可能になります。この機能は MTD でのみ使用します。


#By cleverly predicting the life time of data, it is possible to
#separate long-living data from short-living data and thereby reduce
#the GC overhead later.  Each type of distinc life expectency (vim) can
#have a separate segment open for writing.  Each (level, vim) tupel can
#be open just once.  If an open segment with unknown vim is encountered
#at mount time, it is closed and ignored henceforth.
しか持たないデータとを区別し、その結果後での GC オーバヘッドを削減するこ
とが可能になります。個々の予測寿命 (vim) タイプは独立のセグメントを持ち、
書き込み可能です。各 レベル/vim タプルは一回だけオープン可能です。マウン
ト時に vim の不明な開かれたセグメントを見つけた場合、それは閉じられて以降

#Indirect Tree

#Inodes in LogFS are similar to FFS-style filesystems with direct and
#indirect block pointers.  One difference is that LogFS uses a single
#indirect pointer that can be either a 1x, 2x, etc. indirect pointer.
#A height field in the inode defines the height of the indirect tree
#and thereby the indirection of the pointer.
LogFS の inode は FFS に似たファイルシステムで、直接ブロックポインタと間
接ブロックポインタをもっています。一つの違いは、LogFS では一つの間接ポイ
ンタが 1x 2x などの間接ポインタとなりうる点が異なります。inode の height

#Another difference is the addressing of indirect blocks.  In LogFS,
#the first 16 pointers in the first indirect block are left empty,
#corresponding to the 16 direct pointers in the inode.  In ext2 (maybe
#others as well) the first pointer in the first indirect block
#corresponds to logical block 12, skipping the 12 direct pointers.
#So where ext2 is using arithmetic to better utilize space, LogFS keeps
#arithmetic simple and uses compression to save space.
もう一つの違いは、間接ブロックのアドレス方法にあります。LogFS では、最初
の間接ブロックの初めから 16 個のポインタは空で残され、これは inode の 16
個の直接ブロックのポインタに対応します。ext2 (恐らく他にも) では、最初の
間接ブロックの初めから 12 個のポインタは空で残され、12 個の直接ブロックの
ポインタをスキップしています。つまり、ext2 では計算を行ってスペースの利用
効率をあげているのに対して、LogFS では計算を単純に留めてスペースの節約は


#Both file data and metadata can be compressed.  Compression for file
#data can be enabled with chattr +c and disabled with chattr -c.  Doing
#so has no effect on existing data, but new data will be stored
#accordingly.  New inodes will inherit the compression flag of the
#parent directory.
chattr +c で有効化、chattr -c で無効化できます。この設定は、既存データに
は影響がなく、新規データは設定に従って書き込まれます。新しい inode は、親

#Metadata is always compressed.  However, the space accounting ignores
#this and charges for the uncompressed size.  Failing to do so could
#result in GC failures when, after moving some data, indirect blocks
#compress worse than previously.  Even on a 100% full medium, GC may
#not consume any extra space, so the compression gains are lost space
#to the user.
に間接ブロックが元のデータに比べて圧縮されなかった場合、GC が失敗するため
です。100% 一杯のメディアでも、GC で追加容量を消費することは許されないた

#However, they are not lost space to the filesystem internals.  By
#cheating the user for those bytes, the filesystem gained some slack
#space and GC will run less often and faster.
稼ぎ、GC 実行回数が減りますし、高速に動作するようにもなります。

#Garbage Collection and Wear Leveling

#Garbage collection is invoked whenever the number of free segments
#falls below a threshold.  The best (known) candidate is picked based
#on the least amount of valid data contained in the segment.  All
#remaining valid data is copied elsewhere, thereby invalidating it.
も起動されます。最良の (既知の) 候補が、セグメントに格納されている有効デ

#The GC code also checks for aliases and writes then back if their
#number gets too large.
GC コードではエイリアス数もチェックし、(しきい値を越えるほど) 大きくなっ

#Wear leveling is done by occasionally picking a suboptimal segment for
#garbage collection.  If a stale segments erase count is significantly
#lower than the active segments' erase counts, it will be picked.  Wear
#leveling is rate limited, so it will never monopolize the device for
#more than one segment worth at a time.
々」抽出することで実行されます。無効なセグメントの消去数 (訳注:ページの累
積消去回数) が有効なセグメントの消去回数より「明白に少ない」場合、そのセ

#Values for "occasionally", "significantly lower" are compile time

#Hashed directories

#To satisfy efficient lookup(), directory entries are hashed and
#located based on the hash.  In order to both support large directories
#and not be overly inefficient for small directories, several hash
#tables of increasing size are used.  For each table, the hash value
#modulo the table size gives the table index.
効率的な lookup() を実現するために、ディレクトリエントリはハッシュ化され
てハッシュを元に位置が決定されるようになっています。巨大な (ファイル数の
多い) ディレクトリをサポートし、同時に小さなディレクトリで過度に非効率に
ならないようにするため、サイズが (順に) 大きくなる複数のハッシュテーブル

#Tables sizes are chosen to limit the number of indirect blocks with a
#fully populated table to 0, 1, 2 or 3 respectively.  So the first
#table contains 16 entries, the second 512-16, etc.
テーブルサイズは、順に 0、1、2、3 階層のテーブルに間接ブロックを一杯に格
納した数の制限を元に選択されます。つまり最初のテーブルが 16 エントリを格
納し、二番目が 512-16 エントリを格納し、のようになります。

#The last table is special in several ways.  First its size depends on
#the effective 32bit limit on telldir/seekdir cookies.  Since logfs
#uses the upper half of the address space for indirect blocks, the size
#is limited to 2^31.  Secondly the table contains hash buckets with 16
#entries each.
telldir/seekdir クッキーの 32bit 制限に依存しています。これは、logfs がア
ドレス空間の上半分を間接ブロックに用いているため、サイズが 2^31 に制限さ
れるためです。次に、テーブルには各 16 エントリのハッシュバケットが格納さ

#Using single-entry buckets would result in birthday "attacks".  At
#just 2^16 used entries, hash collisions would be likely (P >= 0.5).
#My math skills are insufficient to do the combinatorics for the 17x
#collisions necessary to overflow a bucket, but testing showed that in
#10,000 runs the lowest directory fill before a bucket overflow was
#188,057,130 entries with an average of 315,149,915 entries.  So for
#directory sizes of up to a million, bucket overflows should be
#virtually impossible under normal circumstances.
す。たった 2^16 エントリしか使っていない場合には、ハッシュ衝突確率は
>=0.5 になるでしょう。数学は得意ではありませんので、バケットを溢れされる
のに必要な 17 回の衝突の組み合わせの計算はできませんが、最下位のディレク
トリを 10,000 回埋める実験の結果によるとバケットが溢れるまで最小で
188,057,130 エントリが作成でき、平均的には 315,149,915 エントリが作成可能
でした。従って、ディレクトリサイズが 1,000,000 以下なら、バケットオーバフ

#With carefully chosen filenames, it is obviously possible to cause an
#overflow with just 21 entries (4 higher tables + 16 entries + 1).  So
#there may be a security concern if a malicious user has write access
#to a directory.
ファイル名を注意深く選択するなら、単に 21 エントリ (4 つの上位テーブル +
16 エントリ + 1) でオーバフローを発生させることができるのもあきらかですか

#Open For Discussion

#Device Address Space

#A device address space is used for caching.  Both block devices and
#MTD provide functions to either read a single page or write a segment.
#Partial segments may be written for data integrity, but where possible
#complete segments are written for performance on simple block device
#flash media.
デバイスアドレス空間はキャッシュのために用います。ブロックデバイスと MTD

#Meta Inodes
メタ inode

#Inodes are stored in the inode file, which is just a regular file for
#most purposes.  At umount time, however, the inode file needs to
#remain open until all dirty inodes are written.  So
#generic_shutdown_super() may not close this inode, but shouldn't
#complain about remaining inodes due to the inode file either.  Same
#goes for mapping inode of the device address space.
inode は inode ファイルに書き込まれます。殆どの目的では、inode ファイルは
単なる普通のファイルですが、umount 時だけは inode ファイルは全てのダーティ
inode の書き込みが完了するまでオープンしておく必要があります。従って、
generic_shutdown_super() ではこの inode をクローズできませんが、この
inode ファイルのために「残っている inode がある」という警告を出すことも許
されません。デバイスアドレス空間でのマップされた inode についても同じ問題

#Currently logfs uses a hack that essentially copies part of fs/inode.c
#code over.  A general solution would be preferred.
現在、logfs では fs/inode.c コードの一部をコピーしたハックで対応していま

#Indirect block mapping

#With compression, the block device (or mapping inode) cannot be used
#to cache indirect blocks.  Some other place is required.  Currently
#logfs uses the top half of each inode's address space.  The low 8TB
#(on 32bit) are filled with file data, the high 8TB are used for
#indirect blocks.
圧縮を用いる場合、ブロックデバイス (およびマッピング inode) は間接ブロッ
す。現在、logfs は各 inode アドレス空間の上半分を使うようになっています。
(32bit の場合) 下位の 8TB にはファイルデータが格納され、上位 8TB は間接ブ

#One problem is that 16TB files created on 64bit systems actually have
#data in the top 8TB.  But files >16TB would cause problems anyway, so
#only the limit has changed.
一つ問題があって、64bit システムで作成された 16TB のファイルには、実際に
上位の 8TB にデータが格納されることになります。ただし、いずれにせよ 16TB

Linux カーネル 3.x/2.6 付属文書一覧へ戻る