Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 1 | ================================================================================ |
| 2 | WHAT IS Flash-Friendly File System (F2FS)? |
| 3 | ================================================================================ |
| 4 | |
| 5 | NAND flash memory-based storage devices, such as SSD, eMMC, and SD cards, have |
| 6 | been equipped on a variety systems ranging from mobile to server systems. Since |
| 7 | they are known to have different characteristics from the conventional rotating |
| 8 | disks, a file system, an upper layer to the storage device, should adapt to the |
| 9 | changes from the sketch in the design level. |
| 10 | |
| 11 | F2FS is a file system exploiting NAND flash memory-based storage devices, which |
| 12 | is based on Log-structured File System (LFS). The design has been focused on |
| 13 | addressing the fundamental issues in LFS, which are snowball effect of wandering |
| 14 | tree and high cleaning overhead. |
| 15 | |
| 16 | Since a NAND flash memory-based storage device shows different characteristic |
| 17 | according to its internal geometry or flash memory management scheme, namely FTL, |
| 18 | F2FS and its tools support various parameters not only for configuring on-disk |
| 19 | layout, but also for selecting allocation and cleaning algorithms. |
| 20 | |
Changman Lee | d51a7fb | 2013-07-04 17:12:47 +0900 | [diff] [blame] | 21 | The following git tree provides the file system formatting tool (mkfs.f2fs), |
| 22 | a consistency checking tool (fsck.f2fs), and a debugging tool (dump.f2fs). |
Jaegeuk Kim | 5bb446a | 2012-11-27 14:36:14 +0900 | [diff] [blame] | 23 | >> git://git.kernel.org/pub/scm/linux/kernel/git/jaegeuk/f2fs-tools.git |
| 24 | |
| 25 | For reporting bugs and sending patches, please use the following mailing list: |
| 26 | >> linux-f2fs-devel@lists.sourceforge.net |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 27 | |
| 28 | ================================================================================ |
| 29 | BACKGROUND AND DESIGN ISSUES |
| 30 | ================================================================================ |
| 31 | |
| 32 | Log-structured File System (LFS) |
| 33 | -------------------------------- |
| 34 | "A log-structured file system writes all modifications to disk sequentially in |
| 35 | a log-like structure, thereby speeding up both file writing and crash recovery. |
| 36 | The log is the only structure on disk; it contains indexing information so that |
| 37 | files can be read back from the log efficiently. In order to maintain large free |
| 38 | areas on disk for fast writing, we divide the log into segments and use a |
| 39 | segment cleaner to compress the live information from heavily fragmented |
| 40 | segments." from Rosenblum, M. and Ousterhout, J. K., 1992, "The design and |
| 41 | implementation of a log-structured file system", ACM Trans. Computer Systems |
| 42 | 10, 1, 26–52. |
| 43 | |
| 44 | Wandering Tree Problem |
| 45 | ---------------------- |
| 46 | In LFS, when a file data is updated and written to the end of log, its direct |
| 47 | pointer block is updated due to the changed location. Then the indirect pointer |
| 48 | block is also updated due to the direct pointer block update. In this manner, |
| 49 | the upper index structures such as inode, inode map, and checkpoint block are |
| 50 | also updated recursively. This problem is called as wandering tree problem [1], |
| 51 | and in order to enhance the performance, it should eliminate or relax the update |
| 52 | propagation as much as possible. |
| 53 | |
| 54 | [1] Bityutskiy, A. 2005. JFFS3 design issues. http://www.linux-mtd.infradead.org/ |
| 55 | |
| 56 | Cleaning Overhead |
| 57 | ----------------- |
| 58 | Since LFS is based on out-of-place writes, it produces so many obsolete blocks |
| 59 | scattered across the whole storage. In order to serve new empty log space, it |
| 60 | needs to reclaim these obsolete blocks seamlessly to users. This job is called |
| 61 | as a cleaning process. |
| 62 | |
| 63 | The process consists of three operations as follows. |
| 64 | 1. A victim segment is selected through referencing segment usage table. |
| 65 | 2. It loads parent index structures of all the data in the victim identified by |
| 66 | segment summary blocks. |
| 67 | 3. It checks the cross-reference between the data and its parent index structure. |
| 68 | 4. It moves valid data selectively. |
| 69 | |
| 70 | This cleaning job may cause unexpected long delays, so the most important goal |
| 71 | is to hide the latencies to users. And also definitely, it should reduce the |
| 72 | amount of valid data to be moved, and move them quickly as well. |
| 73 | |
| 74 | ================================================================================ |
| 75 | KEY FEATURES |
| 76 | ================================================================================ |
| 77 | |
| 78 | Flash Awareness |
| 79 | --------------- |
| 80 | - Enlarge the random write area for better performance, but provide the high |
| 81 | spatial locality |
| 82 | - Align FS data structures to the operational units in FTL as best efforts |
| 83 | |
| 84 | Wandering Tree Problem |
| 85 | ---------------------- |
| 86 | - Use a term, “node”, that represents inodes as well as various pointer blocks |
| 87 | - Introduce Node Address Table (NAT) containing the locations of all the “node” |
| 88 | blocks; this will cut off the update propagation. |
| 89 | |
| 90 | Cleaning Overhead |
| 91 | ----------------- |
| 92 | - Support a background cleaning process |
| 93 | - Support greedy and cost-benefit algorithms for victim selection policies |
| 94 | - Support multi-head logs for static/dynamic hot and cold data separation |
| 95 | - Introduce adaptive logging for efficient block allocation |
| 96 | |
| 97 | ================================================================================ |
| 98 | MOUNT OPTIONS |
| 99 | ================================================================================ |
| 100 | |
Namjae Jeon | 696c018 | 2013-06-16 09:48:48 +0900 | [diff] [blame] | 101 | background_gc=%s Turn on/off cleaning operations, namely garbage |
| 102 | collection, triggered in background when I/O subsystem is |
| 103 | idle. If background_gc=on, it will turn on the garbage |
| 104 | collection and if background_gc=off, garbage collection |
| 105 | will be truned off. |
| 106 | Default value for this option is on. So garbage |
| 107 | collection is on by default. |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 108 | disable_roll_forward Disable the roll-forward recovery routine |
| 109 | discard Issue discard/TRIM commands when a segment is cleaned. |
| 110 | no_heap Disable heap-style segment allocation which finds free |
| 111 | segments for data from the beginning of main area, while |
| 112 | for node from the end of main area. |
| 113 | nouser_xattr Disable Extended User Attributes. Note: xattr is enabled |
| 114 | by default if CONFIG_F2FS_FS_XATTR is selected. |
| 115 | noacl Disable POSIX Access Control List. Note: acl is enabled |
| 116 | by default if CONFIG_F2FS_FS_POSIX_ACL is selected. |
| 117 | active_logs=%u Support configuring the number of active logs. In the |
| 118 | current design, f2fs supports only 2, 4, and 6 logs. |
| 119 | Default number is 6. |
| 120 | disable_ext_identify Disable the extension list configured by mkfs, so f2fs |
| 121 | does not aware of cold files such as media files. |
Jaegeuk Kim | 66e960c | 2013-11-01 11:20:05 +0900 | [diff] [blame] | 122 | inline_xattr Enable the inline xattrs feature. |
Huajun Li | e4024e8 | 2013-11-10 23:13:21 +0800 | [diff] [blame] | 123 | inline_data Enable the inline data feature: New created small(<~3.4k) |
| 124 | files can be written into inode block. |
Chao Yu | d37a868 | 2014-09-24 18:20:23 +0800 | [diff] [blame] | 125 | inline_dentry Enable the inline dir feature: data in new created |
| 126 | directory entries can be written into inode block. The |
| 127 | space of inode block which is used to store inline |
| 128 | dentries is limited to ~3.4k. |
Jaegeuk Kim | 6b4afdd | 2014-04-02 15:34:36 +0900 | [diff] [blame] | 129 | flush_merge Merge concurrent cache_flush commands as much as possible |
| 130 | to eliminate redundant command issues. If the underlying |
| 131 | device handles the cache_flush command relatively slowly, |
| 132 | recommend to enable this option. |
Jaegeuk Kim | 0f7b2ab | 2014-07-23 09:57:31 -0700 | [diff] [blame] | 133 | nobarrier This option can be used if underlying storage guarantees |
| 134 | its cached data should be written to the novolatile area. |
| 135 | If this option is set, no cache_flush commands are issued |
| 136 | but f2fs still guarantees the write ordering of all the |
| 137 | data writes. |
Jaegeuk Kim | d5053a34 | 2014-10-30 22:47:03 -0700 | [diff] [blame] | 138 | fastboot This option is used when a system wants to reduce mount |
| 139 | time as much as possible, even though normal performance |
| 140 | can be sacrificed. |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 141 | |
| 142 | ================================================================================ |
| 143 | DEBUGFS ENTRIES |
| 144 | ================================================================================ |
| 145 | |
| 146 | /sys/kernel/debug/f2fs/ contains information about all the partitions mounted as |
| 147 | f2fs. Each file shows the whole f2fs information. |
| 148 | |
| 149 | /sys/kernel/debug/f2fs/status includes: |
| 150 | - major file system information managed by f2fs currently |
| 151 | - average SIT information about whole segments |
| 152 | - current memory footprint consumed by f2fs. |
| 153 | |
| 154 | ================================================================================ |
Namjae Jeon | b59d0ba | 2013-08-04 23:09:40 +0900 | [diff] [blame] | 155 | SYSFS ENTRIES |
| 156 | ================================================================================ |
| 157 | |
| 158 | Information about mounted f2f2 file systems can be found in |
| 159 | /sys/fs/f2fs. Each mounted filesystem will have a directory in |
| 160 | /sys/fs/f2fs based on its device name (i.e., /sys/fs/f2fs/sda). |
| 161 | The files in each per-device directory are shown in table below. |
| 162 | |
| 163 | Files in /sys/fs/f2fs/<devname> |
| 164 | (see also Documentation/ABI/testing/sysfs-fs-f2fs) |
| 165 | .............................................................................. |
| 166 | File Content |
| 167 | |
| 168 | gc_max_sleep_time This tuning parameter controls the maximum sleep |
| 169 | time for the garbage collection thread. Time is |
| 170 | in milliseconds. |
| 171 | |
| 172 | gc_min_sleep_time This tuning parameter controls the minimum sleep |
| 173 | time for the garbage collection thread. Time is |
| 174 | in milliseconds. |
| 175 | |
| 176 | gc_no_gc_sleep_time This tuning parameter controls the default sleep |
| 177 | time for the garbage collection thread. Time is |
| 178 | in milliseconds. |
| 179 | |
Namjae Jeon | d2dc095 | 2013-08-04 23:10:15 +0900 | [diff] [blame] | 180 | gc_idle This parameter controls the selection of victim |
| 181 | policy for garbage collection. Setting gc_idle = 0 |
| 182 | (default) will disable this option. Setting |
| 183 | gc_idle = 1 will select the Cost Benefit approach |
| 184 | & setting gc_idle = 2 will select the greedy aproach. |
| 185 | |
Jaegeuk Kim | ea91e9b | 2013-10-24 15:49:07 +0900 | [diff] [blame] | 186 | reclaim_segments This parameter controls the number of prefree |
| 187 | segments to be reclaimed. If the number of prefree |
Jaegeuk Kim | 58c4103 | 2014-03-19 14:17:21 +0900 | [diff] [blame] | 188 | segments is larger than the number of segments |
| 189 | in the proportion to the percentage over total |
| 190 | volume size, f2fs tries to conduct checkpoint to |
| 191 | reclaim the prefree segments to free segments. |
| 192 | By default, 5% over total # of segments. |
Jaegeuk Kim | ea91e9b | 2013-10-24 15:49:07 +0900 | [diff] [blame] | 193 | |
Jaegeuk Kim | ba0697e | 2013-12-19 17:44:41 +0900 | [diff] [blame] | 194 | max_small_discards This parameter controls the number of discard |
| 195 | commands that consist small blocks less than 2MB. |
| 196 | The candidates to be discarded are cached until |
| 197 | checkpoint is triggered, and issued during the |
| 198 | checkpoint. By default, it is disabled with 0. |
| 199 | |
Jaegeuk Kim | 216fbd6 | 2013-11-07 13:13:42 +0900 | [diff] [blame] | 200 | ipu_policy This parameter controls the policy of in-place |
| 201 | updates in f2fs. There are five policies: |
Jaegeuk Kim | 9b5f136 | 2014-09-16 18:30:54 -0700 | [diff] [blame] | 202 | 0x01: F2FS_IPU_FORCE, 0x02: F2FS_IPU_SSR, |
| 203 | 0x04: F2FS_IPU_UTIL, 0x08: F2FS_IPU_SSR_UTIL, |
| 204 | 0x10: F2FS_IPU_FSYNC. |
Jaegeuk Kim | 216fbd6 | 2013-11-07 13:13:42 +0900 | [diff] [blame] | 205 | |
| 206 | min_ipu_util This parameter controls the threshold to trigger |
| 207 | in-place-updates. The number indicates percentage |
| 208 | of the filesystem utilization, and used by |
| 209 | F2FS_IPU_UTIL and F2FS_IPU_SSR_UTIL policies. |
| 210 | |
Jaegeuk Kim | c1ce1b0 | 2014-09-10 16:53:02 -0700 | [diff] [blame] | 211 | min_fsync_blocks This parameter controls the threshold to trigger |
| 212 | in-place-updates when F2FS_IPU_FSYNC mode is set. |
| 213 | The number indicates the number of dirty pages |
| 214 | when fsync needs to flush on its call path. If |
| 215 | the number is less than this value, it triggers |
| 216 | in-place-updates. |
| 217 | |
Jaegeuk Kim | 3bac380 | 2014-01-09 21:00:06 +0900 | [diff] [blame] | 218 | max_victim_search This parameter controls the number of trials to |
| 219 | find a victim segment when conducting SSR and |
| 220 | cleaning operations. The default value is 4096 |
| 221 | which covers 8GB block address range. |
| 222 | |
Jaegeuk Kim | ab9fa66 | 2014-02-27 20:09:05 +0900 | [diff] [blame] | 223 | dir_level This parameter controls the directory level to |
| 224 | support large directory. If a directory has a |
| 225 | number of files, it can reduce the file lookup |
| 226 | latency by increasing this dir_level value. |
| 227 | Otherwise, it needs to decrease this value to |
| 228 | reduce the space overhead. The default value is 0. |
| 229 | |
Jaegeuk Kim | cdfc41c | 2014-03-19 13:31:37 +0900 | [diff] [blame] | 230 | ram_thresh This parameter controls the memory footprint used |
| 231 | by free nids and cached nat entries. By default, |
| 232 | 10 is set, which indicates 10 MB / 1 GB RAM. |
| 233 | |
Namjae Jeon | b59d0ba | 2013-08-04 23:09:40 +0900 | [diff] [blame] | 234 | ================================================================================ |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 235 | USAGE |
| 236 | ================================================================================ |
| 237 | |
| 238 | 1. Download userland tools and compile them. |
| 239 | |
| 240 | 2. Skip, if f2fs was compiled statically inside kernel. |
| 241 | Otherwise, insert the f2fs.ko module. |
| 242 | # insmod f2fs.ko |
| 243 | |
| 244 | 3. Create a directory trying to mount |
| 245 | # mkdir /mnt/f2fs |
| 246 | |
| 247 | 4. Format the block device, and then mount as f2fs |
| 248 | # mkfs.f2fs -l label /dev/block_device |
| 249 | # mount -t f2fs /dev/block_device /mnt/f2fs |
| 250 | |
Changman Lee | d51a7fb | 2013-07-04 17:12:47 +0900 | [diff] [blame] | 251 | mkfs.f2fs |
| 252 | --------- |
| 253 | The mkfs.f2fs is for the use of formatting a partition as the f2fs filesystem, |
| 254 | which builds a basic on-disk layout. |
| 255 | |
| 256 | The options consist of: |
Changman Lee | 1571f84 | 2013-04-03 15:26:49 +0900 | [diff] [blame] | 257 | -l [label] : Give a volume label, up to 512 unicode name. |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 258 | -a [0 or 1] : Split start location of each area for heap-based allocation. |
| 259 | 1 is set by default, which performs this. |
| 260 | -o [int] : Set overprovision ratio in percent over volume size. |
| 261 | 5 is set by default. |
| 262 | -s [int] : Set the number of segments per section. |
| 263 | 1 is set by default. |
| 264 | -z [int] : Set the number of sections per zone. |
| 265 | 1 is set by default. |
| 266 | -e [str] : Set basic extension list. e.g. "mp3,gif,mov" |
Changman Lee | 1571f84 | 2013-04-03 15:26:49 +0900 | [diff] [blame] | 267 | -t [0 or 1] : Disable discard command or not. |
| 268 | 1 is set by default, which conducts discard. |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 269 | |
Changman Lee | d51a7fb | 2013-07-04 17:12:47 +0900 | [diff] [blame] | 270 | fsck.f2fs |
| 271 | --------- |
| 272 | The fsck.f2fs is a tool to check the consistency of an f2fs-formatted |
| 273 | partition, which examines whether the filesystem metadata and user-made data |
| 274 | are cross-referenced correctly or not. |
| 275 | Note that, initial version of the tool does not fix any inconsistency. |
| 276 | |
| 277 | The options consist of: |
| 278 | -d debug level [default:0] |
| 279 | |
| 280 | dump.f2fs |
| 281 | --------- |
| 282 | The dump.f2fs shows the information of specific inode and dumps SSA and SIT to |
| 283 | file. Each file is dump_ssa and dump_sit. |
| 284 | |
| 285 | The dump.f2fs is used to debug on-disk data structures of the f2fs filesystem. |
| 286 | It shows on-disk inode information reconized by a given inode number, and is |
| 287 | able to dump all the SSA and SIT entries into predefined files, ./dump_ssa and |
| 288 | ./dump_sit respectively. |
| 289 | |
| 290 | The options consist of: |
| 291 | -d debug level [default:0] |
| 292 | -i inode no (hex) |
| 293 | -s [SIT dump segno from #1~#2 (decimal), for all 0~-1] |
| 294 | -a [SSA dump segno from #1~#2 (decimal), for all 0~-1] |
| 295 | |
| 296 | Examples: |
| 297 | # dump.f2fs -i [ino] /dev/sdx |
| 298 | # dump.f2fs -s 0~-1 /dev/sdx (SIT dump) |
| 299 | # dump.f2fs -a 0~-1 /dev/sdx (SSA dump) |
| 300 | |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 301 | ================================================================================ |
| 302 | DESIGN |
| 303 | ================================================================================ |
| 304 | |
| 305 | On-disk Layout |
| 306 | -------------- |
| 307 | |
| 308 | F2FS divides the whole volume into a number of segments, each of which is fixed |
| 309 | to 2MB in size. A section is composed of consecutive segments, and a zone |
| 310 | consists of a set of sections. By default, section and zone sizes are set to one |
| 311 | segment size identically, but users can easily modify the sizes by mkfs. |
| 312 | |
| 313 | F2FS splits the entire volume into six areas, and all the areas except superblock |
| 314 | consists of multiple segments as described below. |
| 315 | |
| 316 | align with the zone size <-| |
| 317 | |-> align with the segment size |
| 318 | _________________________________________________________________________ |
Huajun Li | 9268cc3 | 2012-12-31 13:59:04 +0800 | [diff] [blame] | 319 | | | | Segment | Node | Segment | | |
| 320 | | Superblock | Checkpoint | Info. | Address | Summary | Main | |
| 321 | | (SB) | (CP) | Table (SIT) | Table (NAT) | Area (SSA) | | |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 322 | |____________|_____2______|______N______|______N______|______N_____|__N___| |
| 323 | . . |
| 324 | . . |
| 325 | . . |
| 326 | ._________________________________________. |
| 327 | |_Segment_|_..._|_Segment_|_..._|_Segment_| |
| 328 | . . |
| 329 | ._________._________ |
| 330 | |_section_|__...__|_ |
| 331 | . . |
| 332 | .________. |
| 333 | |__zone__| |
| 334 | |
| 335 | - Superblock (SB) |
| 336 | : It is located at the beginning of the partition, and there exist two copies |
| 337 | to avoid file system crash. It contains basic partition information and some |
| 338 | default parameters of f2fs. |
| 339 | |
| 340 | - Checkpoint (CP) |
| 341 | : It contains file system information, bitmaps for valid NAT/SIT sets, orphan |
| 342 | inode lists, and summary entries of current active segments. |
| 343 | |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 344 | - Segment Information Table (SIT) |
| 345 | : It contains segment information such as valid block count and bitmap for the |
| 346 | validity of all the blocks. |
| 347 | |
Huajun Li | 9268cc3 | 2012-12-31 13:59:04 +0800 | [diff] [blame] | 348 | - Node Address Table (NAT) |
| 349 | : It is composed of a block address table for all the node blocks stored in |
| 350 | Main area. |
| 351 | |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 352 | - Segment Summary Area (SSA) |
| 353 | : It contains summary entries which contains the owner information of all the |
| 354 | data and node blocks stored in Main area. |
| 355 | |
| 356 | - Main Area |
| 357 | : It contains file and directory data including their indices. |
| 358 | |
| 359 | In order to avoid misalignment between file system and flash-based storage, F2FS |
| 360 | aligns the start block address of CP with the segment size. Also, it aligns the |
| 361 | start block address of Main area with the zone size by reserving some segments |
| 362 | in SSA area. |
| 363 | |
| 364 | Reference the following survey for additional technical details. |
| 365 | https://wiki.linaro.org/WorkingGroups/Kernel/Projects/FlashCardSurvey |
| 366 | |
| 367 | File System Metadata Structure |
| 368 | ------------------------------ |
| 369 | |
| 370 | F2FS adopts the checkpointing scheme to maintain file system consistency. At |
| 371 | mount time, F2FS first tries to find the last valid checkpoint data by scanning |
| 372 | CP area. In order to reduce the scanning time, F2FS uses only two copies of CP. |
| 373 | One of them always indicates the last valid data, which is called as shadow copy |
| 374 | mechanism. In addition to CP, NAT and SIT also adopt the shadow copy mechanism. |
| 375 | |
| 376 | For file system consistency, each CP points to which NAT and SIT copies are |
| 377 | valid, as shown as below. |
| 378 | |
| 379 | +--------+----------+---------+ |
Huajun Li | 9268cc3 | 2012-12-31 13:59:04 +0800 | [diff] [blame] | 380 | | CP | SIT | NAT | |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 381 | +--------+----------+---------+ |
| 382 | . . . . |
| 383 | . . . . |
| 384 | . . . . |
| 385 | +-------+-------+--------+--------+--------+--------+ |
Huajun Li | 9268cc3 | 2012-12-31 13:59:04 +0800 | [diff] [blame] | 386 | | CP #0 | CP #1 | SIT #0 | SIT #1 | NAT #0 | NAT #1 | |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 387 | +-------+-------+--------+--------+--------+--------+ |
| 388 | | ^ ^ |
| 389 | | | | |
| 390 | `----------------------------------------' |
| 391 | |
| 392 | Index Structure |
| 393 | --------------- |
| 394 | |
| 395 | The key data structure to manage the data locations is a "node". Similar to |
| 396 | traditional file structures, F2FS has three types of node: inode, direct node, |
Huajun Li | d08ab08 | 2012-12-05 16:45:32 +0800 | [diff] [blame] | 397 | indirect node. F2FS assigns 4KB to an inode block which contains 923 data block |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 398 | indices, two direct node pointers, two indirect node pointers, and one double |
| 399 | indirect node pointer as described below. One direct node block contains 1018 |
| 400 | data blocks, and one indirect node block contains also 1018 node blocks. Thus, |
| 401 | one inode block (i.e., a file) covers: |
| 402 | |
| 403 | 4KB * (923 + 2 * 1018 + 2 * 1018 * 1018 + 1018 * 1018 * 1018) := 3.94TB. |
| 404 | |
| 405 | Inode block (4KB) |
| 406 | |- data (923) |
| 407 | |- direct node (2) |
| 408 | | `- data (1018) |
| 409 | |- indirect node (2) |
| 410 | | `- direct node (1018) |
| 411 | | `- data (1018) |
| 412 | `- double indirect node (1) |
| 413 | `- indirect node (1018) |
| 414 | `- direct node (1018) |
| 415 | `- data (1018) |
| 416 | |
| 417 | Note that, all the node blocks are mapped by NAT which means the location of |
| 418 | each node is translated by the NAT table. In the consideration of the wandering |
| 419 | tree problem, F2FS is able to cut off the propagation of node updates caused by |
| 420 | leaf data writes. |
| 421 | |
| 422 | Directory Structure |
| 423 | ------------------- |
| 424 | |
| 425 | A directory entry occupies 11 bytes, which consists of the following attributes. |
| 426 | |
| 427 | - hash hash value of the file name |
| 428 | - ino inode number |
| 429 | - len the length of file name |
| 430 | - type file type such as directory, symlink, etc |
| 431 | |
| 432 | A dentry block consists of 214 dentry slots and file names. Therein a bitmap is |
| 433 | used to represent whether each dentry is valid or not. A dentry block occupies |
| 434 | 4KB with the following composition. |
| 435 | |
| 436 | Dentry Block(4 K) = bitmap (27 bytes) + reserved (3 bytes) + |
| 437 | dentries(11 * 214 bytes) + file name (8 * 214 bytes) |
| 438 | |
| 439 | [Bucket] |
| 440 | +--------------------------------+ |
| 441 | |dentry block 1 | dentry block 2 | |
| 442 | +--------------------------------+ |
| 443 | . . |
| 444 | . . |
| 445 | . [Dentry Block Structure: 4KB] . |
| 446 | +--------+----------+----------+------------+ |
| 447 | | bitmap | reserved | dentries | file names | |
| 448 | +--------+----------+----------+------------+ |
| 449 | [Dentry Block: 4KB] . . |
| 450 | . . |
| 451 | . . |
| 452 | +------+------+-----+------+ |
| 453 | | hash | ino | len | type | |
| 454 | +------+------+-----+------+ |
| 455 | [Dentry Structure: 11 bytes] |
| 456 | |
| 457 | F2FS implements multi-level hash tables for directory structure. Each level has |
| 458 | a hash table with dedicated number of hash buckets as shown below. Note that |
| 459 | "A(2B)" means a bucket includes 2 data blocks. |
| 460 | |
| 461 | ---------------------- |
| 462 | A : bucket |
| 463 | B : block |
| 464 | N : MAX_DIR_HASH_DEPTH |
| 465 | ---------------------- |
| 466 | |
| 467 | level #0 | A(2B) |
| 468 | | |
| 469 | level #1 | A(2B) - A(2B) |
| 470 | | |
| 471 | level #2 | A(2B) - A(2B) - A(2B) - A(2B) |
| 472 | . | . . . . |
| 473 | level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B) |
| 474 | . | . . . . |
| 475 | level #N | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B) |
| 476 | |
| 477 | The number of blocks and buckets are determined by, |
| 478 | |
| 479 | ,- 2, if n < MAX_DIR_HASH_DEPTH / 2, |
| 480 | # of blocks in level #n = | |
| 481 | `- 4, Otherwise |
| 482 | |
Chao Yu | bfec07d | 2014-05-28 08:56:09 +0800 | [diff] [blame] | 483 | ,- 2^(n + dir_level), |
| 484 | | if n + dir_level < MAX_DIR_HASH_DEPTH / 2, |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 485 | # of buckets in level #n = | |
Chao Yu | bfec07d | 2014-05-28 08:56:09 +0800 | [diff] [blame] | 486 | `- 2^((MAX_DIR_HASH_DEPTH / 2) - 1), |
| 487 | Otherwise |
Jaegeuk Kim | 98e4da8 | 2012-11-02 17:05:42 +0900 | [diff] [blame] | 488 | |
| 489 | When F2FS finds a file name in a directory, at first a hash value of the file |
| 490 | name is calculated. Then, F2FS scans the hash table in level #0 to find the |
| 491 | dentry consisting of the file name and its inode number. If not found, F2FS |
| 492 | scans the next hash table in level #1. In this way, F2FS scans hash tables in |
| 493 | each levels incrementally from 1 to N. In each levels F2FS needs to scan only |
| 494 | one bucket determined by the following equation, which shows O(log(# of files)) |
| 495 | complexity. |
| 496 | |
| 497 | bucket number to scan in level #n = (hash value) % (# of buckets in level #n) |
| 498 | |
| 499 | In the case of file creation, F2FS finds empty consecutive slots that cover the |
| 500 | file name. F2FS searches the empty slots in the hash tables of whole levels from |
| 501 | 1 to N in the same way as the lookup operation. |
| 502 | |
| 503 | The following figure shows an example of two cases holding children. |
| 504 | --------------> Dir <-------------- |
| 505 | | | |
| 506 | child child |
| 507 | |
| 508 | child - child [hole] - child |
| 509 | |
| 510 | child - child - child [hole] - [hole] - child |
| 511 | |
| 512 | Case 1: Case 2: |
| 513 | Number of children = 6, Number of children = 3, |
| 514 | File size = 7 File size = 7 |
| 515 | |
| 516 | Default Block Allocation |
| 517 | ------------------------ |
| 518 | |
| 519 | At runtime, F2FS manages six active logs inside "Main" area: Hot/Warm/Cold node |
| 520 | and Hot/Warm/Cold data. |
| 521 | |
| 522 | - Hot node contains direct node blocks of directories. |
| 523 | - Warm node contains direct node blocks except hot node blocks. |
| 524 | - Cold node contains indirect node blocks |
| 525 | - Hot data contains dentry blocks |
| 526 | - Warm data contains data blocks except hot and cold data blocks |
| 527 | - Cold data contains multimedia data or migrated data blocks |
| 528 | |
| 529 | LFS has two schemes for free space management: threaded log and copy-and-compac- |
| 530 | tion. The copy-and-compaction scheme which is known as cleaning, is well-suited |
| 531 | for devices showing very good sequential write performance, since free segments |
| 532 | are served all the time for writing new data. However, it suffers from cleaning |
| 533 | overhead under high utilization. Contrarily, the threaded log scheme suffers |
| 534 | from random writes, but no cleaning process is needed. F2FS adopts a hybrid |
| 535 | scheme where the copy-and-compaction scheme is adopted by default, but the |
| 536 | policy is dynamically changed to the threaded log scheme according to the file |
| 537 | system status. |
| 538 | |
| 539 | In order to align F2FS with underlying flash-based storage, F2FS allocates a |
| 540 | segment in a unit of section. F2FS expects that the section size would be the |
| 541 | same as the unit size of garbage collection in FTL. Furthermore, with respect |
| 542 | to the mapping granularity in FTL, F2FS allocates each section of the active |
| 543 | logs from different zones as much as possible, since FTL can write the data in |
| 544 | the active logs into one allocation unit according to its mapping granularity. |
| 545 | |
| 546 | Cleaning process |
| 547 | ---------------- |
| 548 | |
| 549 | F2FS does cleaning both on demand and in the background. On-demand cleaning is |
| 550 | triggered when there are not enough free segments to serve VFS calls. Background |
| 551 | cleaner is operated by a kernel thread, and triggers the cleaning job when the |
| 552 | system is idle. |
| 553 | |
| 554 | F2FS supports two victim selection policies: greedy and cost-benefit algorithms. |
| 555 | In the greedy algorithm, F2FS selects a victim segment having the smallest number |
| 556 | of valid blocks. In the cost-benefit algorithm, F2FS selects a victim segment |
| 557 | according to the segment age and the number of valid blocks in order to address |
| 558 | log block thrashing problem in the greedy algorithm. F2FS adopts the greedy |
| 559 | algorithm for on-demand cleaner, while background cleaner adopts cost-benefit |
| 560 | algorithm. |
| 561 | |
| 562 | In order to identify whether the data in the victim segment are valid or not, |
| 563 | F2FS manages a bitmap. Each bit represents the validity of a block, and the |
| 564 | bitmap is composed of a bit stream covering whole blocks in main area. |