| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-id: <000801cda2f0$672214f0$35663ed0$%kim@samsung.com> Date: Fri, 05 Oct 2012 20:56:06 +0900 From: 김재극 <jaegeuk.kim@...sung.com> To: viro@...iv.linux.org.uk, 'Theodore Ts'o' <tytso@....edu>, gregkh@...uxfoundation.org, linux-kernel@...r.kernel.org, chur.lee@...sung.com, cm224.lee@...sung.com, jaegeuk.kim@...sung.com, jooyoung.hwang@...sung.com Subject: [PATCH 01/16] f2fs: add document This adds a document describing the mount options, proc entries, usage, and design of Flash-Friendly File System, namely F2FS. Signed-off-by: Jaegeuk Kim <jaegeuk.kim@...sung.com> --- Documentation/filesystems/00-INDEX | 2 + Documentation/filesystems/f2fs.txt | 314 ++++++++++++++++++++++++++++++++++++ 2 files changed, 316 insertions(+) create mode 100644 Documentation/filesystems/f2fs.txt diff --git a/Documentation/filesystems/00-INDEX b/Documentation/filesystems/00-INDEX index 8c624a1..ce5fd46 100644 --- a/Documentation/filesystems/00-INDEX +++ b/Documentation/filesystems/00-INDEX @@ -48,6 +48,8 @@ ext4.txt - info, mount options and specifications for the Ext4 filesystem. files.txt - info on file management in the Linux kernel. +f2fs.txt + - info and mount options for the F2FS filesystem. fuse.txt - info on the Filesystem in User SpacE including mount options. gfs2.txt diff --git a/Documentation/filesystems/f2fs.txt b/Documentation/filesystems/f2fs.txt new file mode 100644 index 0000000..cd3f846 --- /dev/null +++ b/Documentation/filesystems/f2fs.txt @@ -0,0 +1,314 @@ +================================================================================ +WHAT IS Flash-Friendly File System (F2FS)? +================================================================================ + +NAND flash memory-based storage devices, such as SSD, eMMC, and SD cards, have +been widely being used for ranging from mobile to server systems. Since they are +known to have different characteristics from the conventional rotational disks, +a file system, an upper layer to the storage device, should adapt to the changes +from the sketch. + +F2FS is a file system exploiting NAND flash memory-based storage devices, which +is based on Log-structured File System (LFS). The design has been focused on +addressing the fundamental issues in LFS, which are snowball effect of wandering +tree and high cleaning overhead. + +Since a NAND flash memory-based storage device shows different characteristic +according to its internal geometry or flash memory management scheme aka FTL, +F2FS and its tools support various parameters not only for configuring on-disk +layout, but also for selecting allocation and cleaning algorithms. + +The file system formatting tool, "mkfs.f2fs", is available from the following +download page: http://sourceforge.net/projects/f2fs-tools/ + +================================================================================ +MOUNT OPTIONS +================================================================================ + +background_gc_off Turn off the cleaning operation, aka garbage collection, + in background triggered when I/O subsystem is idle. +disable_roll_forward Disable the roll-forward recovery routine during SPOR. +discard Issue discard/TRIM commands when a segment is cleaned. +no_heap Disable heap-style segment allocation in which finds free + segments for data from the beginning of main area, while + for node from the end of main area. +nouser_xattr Disable Extened User Attributes. Note: xattr is enabled + by default if CONFIG_F2FS_FS_XATTR is selected. +noacl Disable POSIX Access Control List. Note: acl is enabled + by default if CONFIG_F2FS_FS_POSIX_ACL is selected. + +================================================================================ +PROC ENTRIES +================================================================================ + +/proc/fs/f2fs/ contains information about partitions mounted as f2fs. For each +partition, a corresponding directory, named as its device name, is provided with +the following proc entries. + +- f2fs_stat major file system information managed by f2fs currently +- f2fs_sit_stat average SIT information about whole segments +- f2fs_mem_stat current memory footprint consumed by f2fs + +e.g., in /proc/fs/f2fs/sdb1/ + +================================================================================ +USAGE +================================================================================ + +1. Download userland tools + +2. Insmod f2fs.ko module: + # insmod f2fs.ko + +3. Check the directory trying to mount + # mkdir /mnt/f2fs + +4. Format the block device, and then mount as f2fs + # mkfs.f2fs -l label /dev/block_device + # mount -t f2fs /dev/block_device /mnt/f2fs + +================================================================================ +DESIGN +================================================================================ + +On-disk Layout +-------------- + +F2FS divides whole volume into a number of segments each of which size is 2MB by +default. A section is composed of consecutive segments, and a zone consists of a +set of sections. + +F2FS maintains logically six log areas. Except SB, all the log areas are managed +in a unit of multiple segments. SB is located at the beggining of the partition, +and there exist two superblocks to avoid file system crash. Other file system +metadata such as CP, NAT, SIT, and SSA are located in front part of the volume. +Main area contains file and directory data including their indices. + +Each area manages the following contents. +- CP File system information, bitmaps for valid NAT/SIT sets, orphan + inode lists, and summary entries of current active segments. +- NAT Block address table for all the node blocks stored in Main area. +- SIT Segment information such as valid block count and bitmap for the + validity of all the blocks. +- SSA Summary entries which contains the owner information of all the + data and node blocks stored in Main area. +- Main Node and data blocks. + +In order to avoid misalignment between file system and flash-based storage, F2FS +aligns the start block address of CP with the segment size. Also, it aligns the +start block address of Main area with the zone size by reserving some segments +in SSA area. + + align with the zone size <-| + |-> align with the segment size + _________________________________________________________________________ + | | | Node | Segment | Segment | | + | Superblock | Checkpoint | Address | Info. | Summary | Main | + | (SB) | (CP) | Table (NAT) | Table (SIT) | Area (SSA) | | + |____________|_____2______|______N______|______N______|______N_____|__N___| + . . + . . + . . + ._________________________________________. + |_Segment_|_..._|_Segment_|_..._|_Segment_| + . . + ._________._________ + |_section_|__...__|_ + . . + .________. + |__zone__| + + +File System Metadata Structure +------------------------------ + +F2FS adopts the checkpointing scheme to maintain file system consistency. At the +mount time, F2FS first tries to find the last valid checkpoint data by scanning +CP area. In order to reduce the scanning time, F2FS uses only two copies of CP. +One of them always indicates the last valid data, which is called as shadow copy +mechanism. In addition to CP, NAT and SIT also adopts the shadow copy mechanism. + +For file system consistency, each CP points which NAT and SIT copies are valid, +as shown as below. + + +--------+----------+---------+ + | CP | NAT | SIT | + +--------+----------+---------+ + . . . . + . . . . + . . . . + +-------+-------+--------+--------+--------+--------+ + | CP #0 | CP #1 | NAT #0 | NAT #1 | SIT #0 | SIT #1 | + +-------+-------+--------+--------+--------+--------+ + | ^ ^ + | | | + `----------------------------------------' + +Index Structure +--------------- + +The key data structure to manage the data locations is a "node". As similar as +traditional file structures, F2FS has three types of node: inode, direct node, +indirect node. F2FS assigns 4KB to an inode block where contains 929 data block +indices, two direct node pointers, two indirect node pointers, and one double +indirect node pointer as described below. One direct node block contains 1018 +data blocks, and one indirect node block contains also 1018 node blocks. Thus, +One inode block (i.e., a file) covers: + 4KB * (929 + 2 * 1018 + 2 * 1018 * 1018 + 1018 * 1018 * 1018) := 3.94TB. + + Inode block (4KB) + |- data (929) + |- direct node (2) + | `- data (1018) + |- indirect node (2) + | `- direct node (1018) + | `- data (1018) + `- triple indirect node (1) + `- indirect node (1018) + `- direct node (1018) + `- data (1018) + +Note that, all the node blocks are mapped by NAT, which means the location of +each node is translated by the NAT table. In the consideration of the wandering +tree problem, F2FS is able to cut off the propagation of node updates caused by +leaf data writes. + +Directory Structure +------------------- + +A directory entry occupies 11 bytes, which consists of the following attributes. + +- hash hash value of the file name +- ino inode number +- len the length of file name +- type file type such as directory, symlink, etc + +A dentry block consists of 214 dentry slots and file names. There-in bitmap is +used to represent whether each dentry is valid or not. A dentry block occupies +4KB with the following composition. + + Dentry Block(4 K) = bitmap (27 bytes) + reserved (3 bytes) + + dentries(11 * 214 bytes) + file name (8 * 214 bytes) + + [Bucket] + +--------------------------------+ + |dentry block 1 | dentry block 2 | + +--------------------------------+ + . . + . . + . [Dentry Block Structure: 4KB] . + +--------+----------+----------+------------+ + | bitmap | reserved | dentries | file names | + +--------+----------+----------+------------+ + [Dentry Block: 4KB] . . + . . + . . + +------+------+-----+------+ + | hash | ino | len | type | + +------+------+-----+------+ + [Dentry Structure: 11 bytes] + +F2FS implements multi-level hash tables for directory structure. Each level has +a hash table with dedicated number of hash buckets as shown below. Note that, +"A(2B)" means a bucket includes 2 data blocks. + +---------------------- +A : bucket +B : block +N : MAX_DIR_HASH_DEPTH +---------------------- + +level #0 | A(2B) + | +level #1 | A(2B) - A(2B) + | +level #2 | A(2B) - A(2B) - A(2B) - A(2B) + . | . . . . +level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B) + . | . . . . +level #N | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B) + +The number of blocks and buckets are determined by, + + ,- 2, if n < MAX_DIR_HASH_DEPTH / 2, + # of blocks in level #n = | + `- 4, Otherwise + + ,- 2^n, if n < MAX_DIR_HASH_DEPTH / 2, + # of buckets in level #n = | + `- 2^((MAX_DIR_HASH_DEPTH / 2) - 1), Otherwise + +When F2FS finds a file name in a directory, at first a hash value of the file +name is calculated. Then, F2FS scans the hash table in level #0 to find the +dentry consisting of the file name and its inode number. If not found, F2FS +scans the next hash table in level #1. In this way, F2FS scans hash tables in +each levels incrementally from 1 to N. In each levels, F2FS needs to scan only +one bucket determined by the follow equation, which shows O(log(# of files)) +complexity. + + bucket number to scan in level #n = (hash value) % (# of buckets in level #n) + +In the case of file creation, F2FS finds an empty consecutive slots that covers +the file name. F2FS searches the empty slots in the hash tables of whole levels +from 1 to N in the same way as the lookup operation. + +The following figure shows an example of two cases holding children. + --------------> Dir <-------------- + | | + child child + + child - child [hole] - child + + child - child - child [hole] - [hole] - child + + Case 1: Case 2: + Number of children = 6, Number of children = 3, + File size = 7 File size = 7 + +Default Block Allocation +------------------------ + +In runtime, F2FS manages six active logs inside "Main" area: Hot/Warm/Cold node +and Hot/Warm/Cold data. + +- Hot node contains direct node blocks of directories. +- Warm node contains direct node blocks except hot node blocks. +- Cold node contains indirect node blocks +- Hot data contains dentry blocks +- Warm data contains data blocks except hot and cold data blocks +- Cold data contains multimedia data or migrated data blocks + +LFS has two schemes for free space management: threaded log and copy-and-compac- +tion. The copy-and-compaction scheme, aka cleaning, is well-suited for devices +showing very good sequential write performance, since free segments are served +all the time for writing new data. However, it suffers from cleaning overhead +under high utilization. Contrarily, the threaded log scheme suffers from random +writes, but no cleaning process is needed. F2FS adopts a hybrid scheme where the +copy-and-compaction scheme is adopted by default, but the policy is dynamically +changed to the threaded log scheme according to the file system status. + +In order to align F2FS with underlying flash-based storages, F2FS allocates a +segment in a unit of section. F2FS expects that the section size would be the +same as the unit size of garbage collection in FTL. Furthermore, with respect +to the mapping granularity in FTL, F2FS allocates each sections of the active +logs from different zones as much as possible, since FTL can write the data in +the active logs into one allocation unit according to its mapping granularity. + +Cleaning process +---------------- + +F2FS does cleaning both on demand and in the background. On-demand cleaning is +triggered when there are not enough free segments to serve VFS calls. Background +cleaner is operated by a kernel thread, and triggers the cleaning job when the +system is idle. + +F2FS supports two victim selection policies: greedy and cost-benefit algorithms. +In greedy algorithm, F2FS selects a victim segment having the smallest number of +valid blocks. In cost-benefit algorithm, F2FS selects a victim segment according +to the segment age and the number of valid blocks in order to address log block +thrashing problem in greedy algorithm. F2FS adopts greedy algorithm for on-demand +cleaner, while background cleaner adopts cost-benefit algorithm. + +In order to identify what the data in the victim segment are valid or not, F2FS +manages a bitmap. Each bit represents the validity of a block, and the bitmap is +composed of a bit stream covering whole blocks in main area. -- 1.7.9.5 --- Jaegeuk Kim Samsung -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists