1.. SPDX-License-Identifier: GPL-2.0
2
3==========================================
4WHAT IS Flash-Friendly File System (F2FS)?
5==========================================
6
7NAND flash memory-based storage devices, such as SSD, eMMC, and SD cards, have
8been equipped on a variety systems ranging from mobile to server systems. Since
9they are known to have different characteristics from the conventional rotating
10disks, a file system, an upper layer to the storage device, should adapt to the
11changes from the sketch in the design level.
12
13F2FS is a file system exploiting NAND flash memory-based storage devices, which
14is based on Log-structured File System (LFS). The design has been focused on
15addressing the fundamental issues in LFS, which are snowball effect of wandering
16tree and high cleaning overhead.
17
18Since a NAND flash memory-based storage device shows different characteristic
19according to its internal geometry or flash memory management scheme, namely FTL,
20F2FS and its tools support various parameters not only for configuring on-disk
21layout, but also for selecting allocation and cleaning algorithms.
22
23The following git tree provides the file system formatting tool (mkfs.f2fs),
24a consistency checking tool (fsck.f2fs), and a debugging tool (dump.f2fs).
25
26- git://git.kernel.org/pub/scm/linux/kernel/git/jaegeuk/f2fs-tools.git
27
28For reporting bugs and sending patches, please use the following mailing list:
29
30- linux-f2fs-devel@lists.sourceforge.net
31
32Background and Design issues
33============================
34
35Log-structured File System (LFS)
36--------------------------------
37"A log-structured file system writes all modifications to disk sequentially in
38a log-like structure, thereby speeding up  both file writing and crash recovery.
39The log is the only structure on disk; it contains indexing information so that
40files can be read back from the log efficiently. In order to maintain large free
41areas on disk for fast writing, we divide  the log into segments and use a
42segment cleaner to compress the live information from heavily fragmented
43segments." from Rosenblum, M. and Ousterhout, J. K., 1992, "The design and
44implementation of a log-structured file system", ACM Trans. Computer Systems
4510, 1, 26–52.
46
47Wandering Tree Problem
48----------------------
49In LFS, when a file data is updated and written to the end of log, its direct
50pointer block is updated due to the changed location. Then the indirect pointer
51block is also updated due to the direct pointer block update. In this manner,
52the upper index structures such as inode, inode map, and checkpoint block are
53also updated recursively. This problem is called as wandering tree problem [1],
54and in order to enhance the performance, it should eliminate or relax the update
55propagation as much as possible.
56
57[1] Bityutskiy, A. 2005. JFFS3 design issues. http://www.linux-mtd.infradead.org/
58
59Cleaning Overhead
60-----------------
61Since LFS is based on out-of-place writes, it produces so many obsolete blocks
62scattered across the whole storage. In order to serve new empty log space, it
63needs to reclaim these obsolete blocks seamlessly to users. This job is called
64as a cleaning process.
65
66The process consists of three operations as follows.
67
681. A victim segment is selected through referencing segment usage table.
692. It loads parent index structures of all the data in the victim identified by
70   segment summary blocks.
713. It checks the cross-reference between the data and its parent index structure.
724. It moves valid data selectively.
73
74This cleaning job may cause unexpected long delays, so the most important goal
75is to hide the latencies to users. And also definitely, it should reduce the
76amount of valid data to be moved, and move them quickly as well.
77
78Key Features
79============
80
81Flash Awareness
82---------------
83- Enlarge the random write area for better performance, but provide the high
84  spatial locality
85- Align FS data structures to the operational units in FTL as best efforts
86
87Wandering Tree Problem
88----------------------
89- Use a term, “node”, that represents inodes as well as various pointer blocks
90- Introduce Node Address Table (NAT) containing the locations of all the “node”
91  blocks; this will cut off the update propagation.
92
93Cleaning Overhead
94-----------------
95- Support a background cleaning process
96- Support greedy and cost-benefit algorithms for victim selection policies
97- Support multi-head logs for static/dynamic hot and cold data separation
98- Introduce adaptive logging for efficient block allocation
99
100Mount Options
101=============
102
103
104====================== ============================================================
105background_gc=%s       Turn on/off cleaning operations, namely garbage
106                       collection, triggered in background when I/O subsystem is
107                       idle. If background_gc=on, it will turn on the garbage
108                       collection and if background_gc=off, garbage collection
109                       will be turned off. If background_gc=sync, it will turn
110                       on synchronous garbage collection running in background.
111                       Default value for this option is on. So garbage
112                       collection is on by default.
113disable_roll_forward   Disable the roll-forward recovery routine
114norecovery             Disable the roll-forward recovery routine, mounted read-
115                       only (i.e., -o ro,disable_roll_forward)
116discard/nodiscard      Enable/disable real-time discard in f2fs, if discard is
117                       enabled, f2fs will issue discard/TRIM commands when a
118		       segment is cleaned.
119no_heap                Disable heap-style segment allocation which finds free
120                       segments for data from the beginning of main area, while
121		       for node from the end of main area.
122nouser_xattr           Disable Extended User Attributes. Note: xattr is enabled
123                       by default if CONFIG_F2FS_FS_XATTR is selected.
124noacl                  Disable POSIX Access Control List. Note: acl is enabled
125                       by default if CONFIG_F2FS_FS_POSIX_ACL is selected.
126active_logs=%u         Support configuring the number of active logs. In the
127                       current design, f2fs supports only 2, 4, and 6 logs.
128                       Default number is 6.
129disable_ext_identify   Disable the extension list configured by mkfs, so f2fs
130                       does not aware of cold files such as media files.
131inline_xattr           Enable the inline xattrs feature.
132noinline_xattr         Disable the inline xattrs feature.
133inline_xattr_size=%u   Support configuring inline xattr size, it depends on
134		       flexible inline xattr feature.
135inline_data            Enable the inline data feature: New created small(<~3.4k)
136                       files can be written into inode block.
137inline_dentry          Enable the inline dir feature: data in new created
138                       directory entries can be written into inode block. The
139                       space of inode block which is used to store inline
140                       dentries is limited to ~3.4k.
141noinline_dentry        Disable the inline dentry feature.
142flush_merge	       Merge concurrent cache_flush commands as much as possible
143                       to eliminate redundant command issues. If the underlying
144		       device handles the cache_flush command relatively slowly,
145		       recommend to enable this option.
146nobarrier              This option can be used if underlying storage guarantees
147                       its cached data should be written to the novolatile area.
148		       If this option is set, no cache_flush commands are issued
149		       but f2fs still guarantees the write ordering of all the
150		       data writes.
151fastboot               This option is used when a system wants to reduce mount
152                       time as much as possible, even though normal performance
153		       can be sacrificed.
154extent_cache           Enable an extent cache based on rb-tree, it can cache
155                       as many as extent which map between contiguous logical
156                       address and physical address per inode, resulting in
157                       increasing the cache hit ratio. Set by default.
158noextent_cache         Disable an extent cache based on rb-tree explicitly, see
159                       the above extent_cache mount option.
160noinline_data          Disable the inline data feature, inline data feature is
161                       enabled by default.
162data_flush             Enable data flushing before checkpoint in order to
163                       persist data of regular and symlink.
164reserve_root=%d        Support configuring reserved space which is used for
165                       allocation from a privileged user with specified uid or
166                       gid, unit: 4KB, the default limit is 0.2% of user blocks.
167resuid=%d              The user ID which may use the reserved blocks.
168resgid=%d              The group ID which may use the reserved blocks.
169fault_injection=%d     Enable fault injection in all supported types with
170                       specified injection rate.
171fault_type=%d          Support configuring fault injection type, should be
172                       enabled with fault_injection option, fault type value
173                       is shown below, it supports single or combined type.
174
175                       ===================	===========
176                       Type_Name		Type_Value
177                       ===================	===========
178                       FAULT_KMALLOC		0x000000001
179                       FAULT_KVMALLOC		0x000000002
180                       FAULT_PAGE_ALLOC		0x000000004
181                       FAULT_PAGE_GET		0x000000008
182                       FAULT_ALLOC_BIO		0x000000010
183                       FAULT_ALLOC_NID		0x000000020
184                       FAULT_ORPHAN		0x000000040
185                       FAULT_BLOCK		0x000000080
186                       FAULT_DIR_DEPTH		0x000000100
187                       FAULT_EVICT_INODE	0x000000200
188                       FAULT_TRUNCATE		0x000000400
189                       FAULT_READ_IO		0x000000800
190                       FAULT_CHECKPOINT		0x000001000
191                       FAULT_DISCARD		0x000002000
192                       FAULT_WRITE_IO		0x000004000
193                       ===================	===========
194mode=%s                Control block allocation mode which supports "adaptive"
195                       and "lfs". In "lfs" mode, there should be no random
196                       writes towards main area.
197io_bits=%u             Set the bit size of write IO requests. It should be set
198                       with "mode=lfs".
199usrquota               Enable plain user disk quota accounting.
200grpquota               Enable plain group disk quota accounting.
201prjquota               Enable plain project quota accounting.
202usrjquota=<file>       Appoint specified file and type during mount, so that quota
203grpjquota=<file>       information can be properly updated during recovery flow,
204prjjquota=<file>       <quota file>: must be in root directory;
205jqfmt=<quota type>     <quota type>: [vfsold,vfsv0,vfsv1].
206offusrjquota           Turn off user journelled quota.
207offgrpjquota           Turn off group journelled quota.
208offprjjquota           Turn off project journelled quota.
209quota                  Enable plain user disk quota accounting.
210noquota                Disable all plain disk quota option.
211whint_mode=%s          Control which write hints are passed down to block
212                       layer. This supports "off", "user-based", and
213                       "fs-based".  In "off" mode (default), f2fs does not pass
214                       down hints. In "user-based" mode, f2fs tries to pass
215                       down hints given by users. And in "fs-based" mode, f2fs
216                       passes down hints with its policy.
217alloc_mode=%s          Adjust block allocation policy, which supports "reuse"
218                       and "default".
219fsync_mode=%s          Control the policy of fsync. Currently supports "posix",
220                       "strict", and "nobarrier". In "posix" mode, which is
221                       default, fsync will follow POSIX semantics and does a
222                       light operation to improve the filesystem performance.
223                       In "strict" mode, fsync will be heavy and behaves in line
224                       with xfs, ext4 and btrfs, where xfstest generic/342 will
225                       pass, but the performance will regress. "nobarrier" is
226                       based on "posix", but doesn't issue flush command for
227                       non-atomic files likewise "nobarrier" mount option.
228test_dummy_encryption  Enable dummy encryption, which provides a fake fscrypt
229                       context. The fake fscrypt context is used by xfstests.
230checkpoint=%s[:%u[%]]  Set to "disable" to turn off checkpointing. Set to "enable"
231                       to reenable checkpointing. Is enabled by default. While
232                       disabled, any unmounting or unexpected shutdowns will cause
233                       the filesystem contents to appear as they did when the
234                       filesystem was mounted with that option.
235                       While mounting with checkpoint=disabled, the filesystem must
236                       run garbage collection to ensure that all available space can
237                       be used. If this takes too much time, the mount may return
238                       EAGAIN. You may optionally add a value to indicate how much
239                       of the disk you would be willing to temporarily give up to
240                       avoid additional garbage collection. This can be given as a
241                       number of blocks, or as a percent. For instance, mounting
242                       with checkpoint=disable:100% would always succeed, but it may
243                       hide up to all remaining free space. The actual space that
244                       would be unusable can be viewed at /sys/fs/f2fs/<disk>/unusable
245                       This space is reclaimed once checkpoint=enable.
246compress_algorithm=%s  Control compress algorithm, currently f2fs supports "lzo",
247                       "lz4" and "zstd" algorithm.
248compress_log_size=%u   Support configuring compress cluster size, the size will
249                       be 4KB * (1 << %u), 16KB is minimum size, also it's
250                       default size.
251compress_extension=%s  Support adding specified extension, so that f2fs can enable
252                       compression on those corresponding files, e.g. if all files
253                       with '.ext' has high compression rate, we can set the '.ext'
254                       on compression extension list and enable compression on
255                       these file by default rather than to enable it via ioctl.
256                       For other files, we can still enable compression via ioctl.
257====================== ============================================================
258
259Debugfs Entries
260===============
261
262/sys/kernel/debug/f2fs/ contains information about all the partitions mounted as
263f2fs. Each file shows the whole f2fs information.
264
265/sys/kernel/debug/f2fs/status includes:
266
267 - major file system information managed by f2fs currently
268 - average SIT information about whole segments
269 - current memory footprint consumed by f2fs.
270
271Sysfs Entries
272=============
273
274Information about mounted f2fs file systems can be found in
275/sys/fs/f2fs.  Each mounted filesystem will have a directory in
276/sys/fs/f2fs based on its device name (i.e., /sys/fs/f2fs/sda).
277The files in each per-device directory are shown in table below.
278
279Files in /sys/fs/f2fs/<devname>
280(see also Documentation/ABI/testing/sysfs-fs-f2fs)
281
282Usage
283=====
284
2851. Download userland tools and compile them.
286
2872. Skip, if f2fs was compiled statically inside kernel.
288   Otherwise, insert the f2fs.ko module::
289
290	# insmod f2fs.ko
291
2923. Create a directory trying to mount::
293
294	# mkdir /mnt/f2fs
295
2964. Format the block device, and then mount as f2fs::
297
298	# mkfs.f2fs -l label /dev/block_device
299	# mount -t f2fs /dev/block_device /mnt/f2fs
300
301mkfs.f2fs
302---------
303The mkfs.f2fs is for the use of formatting a partition as the f2fs filesystem,
304which builds a basic on-disk layout.
305
306The options consist of:
307
308===============    ===========================================================
309``-l [label]``     Give a volume label, up to 512 unicode name.
310``-a [0 or 1]``    Split start location of each area for heap-based allocation.
311
312                   1 is set by default, which performs this.
313``-o [int]``       Set overprovision ratio in percent over volume size.
314
315                   5 is set by default.
316``-s [int]``       Set the number of segments per section.
317
318                   1 is set by default.
319``-z [int]``       Set the number of sections per zone.
320
321                   1 is set by default.
322``-e [str]``       Set basic extension list. e.g. "mp3,gif,mov"
323``-t [0 or 1]``    Disable discard command or not.
324
325                   1 is set by default, which conducts discard.
326===============    ===========================================================
327
328fsck.f2fs
329---------
330The fsck.f2fs is a tool to check the consistency of an f2fs-formatted
331partition, which examines whether the filesystem metadata and user-made data
332are cross-referenced correctly or not.
333Note that, initial version of the tool does not fix any inconsistency.
334
335The options consist of::
336
337  -d debug level [default:0]
338
339dump.f2fs
340---------
341The dump.f2fs shows the information of specific inode and dumps SSA and SIT to
342file. Each file is dump_ssa and dump_sit.
343
344The dump.f2fs is used to debug on-disk data structures of the f2fs filesystem.
345It shows on-disk inode information recognized by a given inode number, and is
346able to dump all the SSA and SIT entries into predefined files, ./dump_ssa and
347./dump_sit respectively.
348
349The options consist of::
350
351  -d debug level [default:0]
352  -i inode no (hex)
353  -s [SIT dump segno from #1~#2 (decimal), for all 0~-1]
354  -a [SSA dump segno from #1~#2 (decimal), for all 0~-1]
355
356Examples::
357
358    # dump.f2fs -i [ino] /dev/sdx
359    # dump.f2fs -s 0~-1 /dev/sdx (SIT dump)
360    # dump.f2fs -a 0~-1 /dev/sdx (SSA dump)
361
362Design
363======
364
365On-disk Layout
366--------------
367
368F2FS divides the whole volume into a number of segments, each of which is fixed
369to 2MB in size. A section is composed of consecutive segments, and a zone
370consists of a set of sections. By default, section and zone sizes are set to one
371segment size identically, but users can easily modify the sizes by mkfs.
372
373F2FS splits the entire volume into six areas, and all the areas except superblock
374consists of multiple segments as described below::
375
376                                            align with the zone size <-|
377                 |-> align with the segment size
378     _________________________________________________________________________
379    |            |            |   Segment   |    Node     |   Segment  |      |
380    | Superblock | Checkpoint |    Info.    |   Address   |   Summary  | Main |
381    |    (SB)    |   (CP)     | Table (SIT) | Table (NAT) | Area (SSA) |      |
382    |____________|_____2______|______N______|______N______|______N_____|__N___|
383                                                                       .      .
384                                                             .                .
385                                                 .                            .
386                                    ._________________________________________.
387                                    |_Segment_|_..._|_Segment_|_..._|_Segment_|
388                                    .           .
389                                    ._________._________
390                                    |_section_|__...__|_
391                                    .            .
392		                    .________.
393	                            |__zone__|
394
395- Superblock (SB)
396   It is located at the beginning of the partition, and there exist two copies
397   to avoid file system crash. It contains basic partition information and some
398   default parameters of f2fs.
399
400- Checkpoint (CP)
401   It contains file system information, bitmaps for valid NAT/SIT sets, orphan
402   inode lists, and summary entries of current active segments.
403
404- Segment Information Table (SIT)
405   It contains segment information such as valid block count and bitmap for the
406   validity of all the blocks.
407
408- Node Address Table (NAT)
409   It is composed of a block address table for all the node blocks stored in
410   Main area.
411
412- Segment Summary Area (SSA)
413   It contains summary entries which contains the owner information of all the
414   data and node blocks stored in Main area.
415
416- Main Area
417   It contains file and directory data including their indices.
418
419In order to avoid misalignment between file system and flash-based storage, F2FS
420aligns the start block address of CP with the segment size. Also, it aligns the
421start block address of Main area with the zone size by reserving some segments
422in SSA area.
423
424Reference the following survey for additional technical details.
425https://wiki.linaro.org/WorkingGroups/Kernel/Projects/FlashCardSurvey
426
427File System Metadata Structure
428------------------------------
429
430F2FS adopts the checkpointing scheme to maintain file system consistency. At
431mount time, F2FS first tries to find the last valid checkpoint data by scanning
432CP area. In order to reduce the scanning time, F2FS uses only two copies of CP.
433One of them always indicates the last valid data, which is called as shadow copy
434mechanism. In addition to CP, NAT and SIT also adopt the shadow copy mechanism.
435
436For file system consistency, each CP points to which NAT and SIT copies are
437valid, as shown as below::
438
439  +--------+----------+---------+
440  |   CP   |    SIT   |   NAT   |
441  +--------+----------+---------+
442  .         .          .          .
443  .            .              .              .
444  .               .                 .                 .
445  +-------+-------+--------+--------+--------+--------+
446  | CP #0 | CP #1 | SIT #0 | SIT #1 | NAT #0 | NAT #1 |
447  +-------+-------+--------+--------+--------+--------+
448     |             ^                          ^
449     |             |                          |
450     `----------------------------------------'
451
452Index Structure
453---------------
454
455The key data structure to manage the data locations is a "node". Similar to
456traditional file structures, F2FS has three types of node: inode, direct node,
457indirect node. F2FS assigns 4KB to an inode block which contains 923 data block
458indices, two direct node pointers, two indirect node pointers, and one double
459indirect node pointer as described below. One direct node block contains 1018
460data blocks, and one indirect node block contains also 1018 node blocks. Thus,
461one inode block (i.e., a file) covers::
462
463  4KB * (923 + 2 * 1018 + 2 * 1018 * 1018 + 1018 * 1018 * 1018) := 3.94TB.
464
465   Inode block (4KB)
466     |- data (923)
467     |- direct node (2)
468     |          `- data (1018)
469     |- indirect node (2)
470     |            `- direct node (1018)
471     |                       `- data (1018)
472     `- double indirect node (1)
473                         `- indirect node (1018)
474			              `- direct node (1018)
475	                                         `- data (1018)
476
477Note that, all the node blocks are mapped by NAT which means the location of
478each node is translated by the NAT table. In the consideration of the wandering
479tree problem, F2FS is able to cut off the propagation of node updates caused by
480leaf data writes.
481
482Directory Structure
483-------------------
484
485A directory entry occupies 11 bytes, which consists of the following attributes.
486
487- hash		hash value of the file name
488- ino		inode number
489- len		the length of file name
490- type		file type such as directory, symlink, etc
491
492A dentry block consists of 214 dentry slots and file names. Therein a bitmap is
493used to represent whether each dentry is valid or not. A dentry block occupies
4944KB with the following composition.
495
496::
497
498  Dentry Block(4 K) = bitmap (27 bytes) + reserved (3 bytes) +
499	              dentries(11 * 214 bytes) + file name (8 * 214 bytes)
500
501                         [Bucket]
502             +--------------------------------+
503             |dentry block 1 | dentry block 2 |
504             +--------------------------------+
505             .               .
506       .                             .
507  .       [Dentry Block Structure: 4KB]       .
508  +--------+----------+----------+------------+
509  | bitmap | reserved | dentries | file names |
510  +--------+----------+----------+------------+
511  [Dentry Block: 4KB] .   .
512		 .               .
513            .                          .
514            +------+------+-----+------+
515            | hash | ino  | len | type |
516            +------+------+-----+------+
517            [Dentry Structure: 11 bytes]
518
519F2FS implements multi-level hash tables for directory structure. Each level has
520a hash table with dedicated number of hash buckets as shown below. Note that
521"A(2B)" means a bucket includes 2 data blocks.
522
523::
524
525    ----------------------
526    A : bucket
527    B : block
528    N : MAX_DIR_HASH_DEPTH
529    ----------------------
530
531    level #0   | A(2B)
532	    |
533    level #1   | A(2B) - A(2B)
534	    |
535    level #2   | A(2B) - A(2B) - A(2B) - A(2B)
536	.     |   .       .       .       .
537    level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B)
538	.     |   .       .       .       .
539    level #N   | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B)
540
541The number of blocks and buckets are determined by::
542
543                            ,- 2, if n < MAX_DIR_HASH_DEPTH / 2,
544  # of blocks in level #n = |
545                            `- 4, Otherwise
546
547                             ,- 2^(n + dir_level),
548			     |        if n + dir_level < MAX_DIR_HASH_DEPTH / 2,
549  # of buckets in level #n = |
550                             `- 2^((MAX_DIR_HASH_DEPTH / 2) - 1),
551			              Otherwise
552
553When F2FS finds a file name in a directory, at first a hash value of the file
554name is calculated. Then, F2FS scans the hash table in level #0 to find the
555dentry consisting of the file name and its inode number. If not found, F2FS
556scans the next hash table in level #1. In this way, F2FS scans hash tables in
557each levels incrementally from 1 to N. In each levels F2FS needs to scan only
558one bucket determined by the following equation, which shows O(log(# of files))
559complexity::
560
561  bucket number to scan in level #n = (hash value) % (# of buckets in level #n)
562
563In the case of file creation, F2FS finds empty consecutive slots that cover the
564file name. F2FS searches the empty slots in the hash tables of whole levels from
5651 to N in the same way as the lookup operation.
566
567The following figure shows an example of two cases holding children::
568
569       --------------> Dir <--------------
570       |                                 |
571    child                             child
572
573    child - child                     [hole] - child
574
575    child - child - child             [hole] - [hole] - child
576
577   Case 1:                           Case 2:
578   Number of children = 6,           Number of children = 3,
579   File size = 7                     File size = 7
580
581Default Block Allocation
582------------------------
583
584At runtime, F2FS manages six active logs inside "Main" area: Hot/Warm/Cold node
585and Hot/Warm/Cold data.
586
587- Hot node	contains direct node blocks of directories.
588- Warm node	contains direct node blocks except hot node blocks.
589- Cold node	contains indirect node blocks
590- Hot data	contains dentry blocks
591- Warm data	contains data blocks except hot and cold data blocks
592- Cold data	contains multimedia data or migrated data blocks
593
594LFS has two schemes for free space management: threaded log and copy-and-compac-
595tion. The copy-and-compaction scheme which is known as cleaning, is well-suited
596for devices showing very good sequential write performance, since free segments
597are served all the time for writing new data. However, it suffers from cleaning
598overhead under high utilization. Contrarily, the threaded log scheme suffers
599from random writes, but no cleaning process is needed. F2FS adopts a hybrid
600scheme where the copy-and-compaction scheme is adopted by default, but the
601policy is dynamically changed to the threaded log scheme according to the file
602system status.
603
604In order to align F2FS with underlying flash-based storage, F2FS allocates a
605segment in a unit of section. F2FS expects that the section size would be the
606same as the unit size of garbage collection in FTL. Furthermore, with respect
607to the mapping granularity in FTL, F2FS allocates each section of the active
608logs from different zones as much as possible, since FTL can write the data in
609the active logs into one allocation unit according to its mapping granularity.
610
611Cleaning process
612----------------
613
614F2FS does cleaning both on demand and in the background. On-demand cleaning is
615triggered when there are not enough free segments to serve VFS calls. Background
616cleaner is operated by a kernel thread, and triggers the cleaning job when the
617system is idle.
618
619F2FS supports two victim selection policies: greedy and cost-benefit algorithms.
620In the greedy algorithm, F2FS selects a victim segment having the smallest number
621of valid blocks. In the cost-benefit algorithm, F2FS selects a victim segment
622according to the segment age and the number of valid blocks in order to address
623log block thrashing problem in the greedy algorithm. F2FS adopts the greedy
624algorithm for on-demand cleaner, while background cleaner adopts cost-benefit
625algorithm.
626
627In order to identify whether the data in the victim segment are valid or not,
628F2FS manages a bitmap. Each bit represents the validity of a block, and the
629bitmap is composed of a bit stream covering whole blocks in main area.
630
631Write-hint Policy
632-----------------
633
6341) whint_mode=off. F2FS only passes down WRITE_LIFE_NOT_SET.
635
6362) whint_mode=user-based. F2FS tries to pass down hints given by
637users.
638
639===================== ======================== ===================
640User                  F2FS                     Block
641===================== ======================== ===================
642                      META                     WRITE_LIFE_NOT_SET
643                      HOT_NODE                 "
644                      WARM_NODE                "
645                      COLD_NODE                "
646ioctl(COLD)           COLD_DATA                WRITE_LIFE_EXTREME
647extension list        "                        "
648
649-- buffered io
650WRITE_LIFE_EXTREME    COLD_DATA                WRITE_LIFE_EXTREME
651WRITE_LIFE_SHORT      HOT_DATA                 WRITE_LIFE_SHORT
652WRITE_LIFE_NOT_SET    WARM_DATA                WRITE_LIFE_NOT_SET
653WRITE_LIFE_NONE       "                        "
654WRITE_LIFE_MEDIUM     "                        "
655WRITE_LIFE_LONG       "                        "
656
657-- direct io
658WRITE_LIFE_EXTREME    COLD_DATA                WRITE_LIFE_EXTREME
659WRITE_LIFE_SHORT      HOT_DATA                 WRITE_LIFE_SHORT
660WRITE_LIFE_NOT_SET    WARM_DATA                WRITE_LIFE_NOT_SET
661WRITE_LIFE_NONE       "                        WRITE_LIFE_NONE
662WRITE_LIFE_MEDIUM     "                        WRITE_LIFE_MEDIUM
663WRITE_LIFE_LONG       "                        WRITE_LIFE_LONG
664===================== ======================== ===================
665
6663) whint_mode=fs-based. F2FS passes down hints with its policy.
667
668===================== ======================== ===================
669User                  F2FS                     Block
670===================== ======================== ===================
671                      META                     WRITE_LIFE_MEDIUM;
672                      HOT_NODE                 WRITE_LIFE_NOT_SET
673                      WARM_NODE                "
674                      COLD_NODE                WRITE_LIFE_NONE
675ioctl(COLD)           COLD_DATA                WRITE_LIFE_EXTREME
676extension list        "                        "
677
678-- buffered io
679WRITE_LIFE_EXTREME    COLD_DATA                WRITE_LIFE_EXTREME
680WRITE_LIFE_SHORT      HOT_DATA                 WRITE_LIFE_SHORT
681WRITE_LIFE_NOT_SET    WARM_DATA                WRITE_LIFE_LONG
682WRITE_LIFE_NONE       "                        "
683WRITE_LIFE_MEDIUM     "                        "
684WRITE_LIFE_LONG       "                        "
685
686-- direct io
687WRITE_LIFE_EXTREME    COLD_DATA                WRITE_LIFE_EXTREME
688WRITE_LIFE_SHORT      HOT_DATA                 WRITE_LIFE_SHORT
689WRITE_LIFE_NOT_SET    WARM_DATA                WRITE_LIFE_NOT_SET
690WRITE_LIFE_NONE       "                        WRITE_LIFE_NONE
691WRITE_LIFE_MEDIUM     "                        WRITE_LIFE_MEDIUM
692WRITE_LIFE_LONG       "                        WRITE_LIFE_LONG
693===================== ======================== ===================
694
695Fallocate(2) Policy
696-------------------
697
698The default policy follows the below posix rule.
699
700Allocating disk space
701    The default operation (i.e., mode is zero) of fallocate() allocates
702    the disk space within the range specified by offset and len.  The
703    file size (as reported by stat(2)) will be changed if offset+len is
704    greater than the file size.  Any subregion within the range specified
705    by offset and len that did not contain data before the call will be
706    initialized to zero.  This default behavior closely resembles the
707    behavior of the posix_fallocate(3) library function, and is intended
708    as a method of optimally implementing that function.
709
710However, once F2FS receives ioctl(fd, F2FS_IOC_SET_PIN_FILE) in prior to
711fallocate(fd, DEFAULT_MODE), it allocates on-disk blocks addressess having
712zero or random data, which is useful to the below scenario where:
713
714 1. create(fd)
715 2. ioctl(fd, F2FS_IOC_SET_PIN_FILE)
716 3. fallocate(fd, 0, 0, size)
717 4. address = fibmap(fd, offset)
718 5. open(blkdev)
719 6. write(blkdev, address)
720
721Compression implementation
722--------------------------
723
724- New term named cluster is defined as basic unit of compression, file can
725  be divided into multiple clusters logically. One cluster includes 4 << n
726  (n >= 0) logical pages, compression size is also cluster size, each of
727  cluster can be compressed or not.
728
729- In cluster metadata layout, one special block address is used to indicate
730  cluster is compressed one or normal one, for compressed cluster, following
731  metadata maps cluster to [1, 4 << n - 1] physical blocks, in where f2fs
732  stores data including compress header and compressed data.
733
734- In order to eliminate write amplification during overwrite, F2FS only
735  support compression on write-once file, data can be compressed only when
736  all logical blocks in file are valid and cluster compress ratio is lower
737  than specified threshold.
738
739- To enable compression on regular inode, there are three ways:
740
741  * chattr +c file
742  * chattr +c dir; touch dir/file
743  * mount w/ -o compress_extension=ext; touch file.ext
744
745Compress metadata layout::
746
747				[Dnode Structure]
748		+-----------------------------------------------+
749		| cluster 1 | cluster 2 | ......... | cluster N |
750		+-----------------------------------------------+
751		.           .                       .           .
752	.                       .                .                      .
753    .         Compressed Cluster       .        .        Normal Cluster            .
754    +----------+---------+---------+---------+  +---------+---------+---------+---------+
755    |compr flag| block 1 | block 2 | block 3 |  | block 1 | block 2 | block 3 | block 4 |
756    +----------+---------+---------+---------+  +---------+---------+---------+---------+
757	    .                             .
758	    .                                           .
759	.                                                           .
760	+-------------+-------------+----------+----------------------------+
761	| data length | data chksum | reserved |      compressed data       |
762	+-------------+-------------+----------+----------------------------+
763