Commit | Line | Data |
---|---|---|
98e4da8c JK |
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 | ||
d51a7fba CL |
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). | |
5bb446a2 JK |
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 | |
98e4da8c JK |
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 | ||
696c018c NJ |
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 | |
c1286ff4 | 105 | will be turned off. If background_gc=sync, it will turn |
6aefd93b | 106 | on synchronous garbage collection running in background. |
696c018c NJ |
107 | Default value for this option is on. So garbage |
108 | collection is on by default. | |
98e4da8c | 109 | disable_roll_forward Disable the roll-forward recovery routine |
2d834bf9 JK |
110 | norecovery Disable the roll-forward recovery routine, mounted read- |
111 | only (i.e., -o ro,disable_roll_forward) | |
c1286ff4 JK |
112 | discard/nodiscard Enable/disable real-time discard in f2fs, if discard is |
113 | enabled, f2fs will issue discard/TRIM commands when a | |
114 | segment is cleaned. | |
98e4da8c JK |
115 | no_heap Disable heap-style segment allocation which finds free |
116 | segments for data from the beginning of main area, while | |
117 | for node from the end of main area. | |
118 | nouser_xattr Disable Extended User Attributes. Note: xattr is enabled | |
119 | by default if CONFIG_F2FS_FS_XATTR is selected. | |
120 | noacl Disable POSIX Access Control List. Note: acl is enabled | |
121 | by default if CONFIG_F2FS_FS_POSIX_ACL is selected. | |
122 | active_logs=%u Support configuring the number of active logs. In the | |
123 | current design, f2fs supports only 2, 4, and 6 logs. | |
124 | Default number is 6. | |
125 | disable_ext_identify Disable the extension list configured by mkfs, so f2fs | |
126 | does not aware of cold files such as media files. | |
66e960c6 | 127 | inline_xattr Enable the inline xattrs feature. |
13f00235 | 128 | noinline_xattr Disable the inline xattrs feature. |
e4024e86 HL |
129 | inline_data Enable the inline data feature: New created small(<~3.4k) |
130 | files can be written into inode block. | |
d37a868f CY |
131 | inline_dentry Enable the inline dir feature: data in new created |
132 | directory entries can be written into inode block. The | |
133 | space of inode block which is used to store inline | |
134 | dentries is limited to ~3.4k. | |
c1286ff4 | 135 | noinline_dentry Diable the inline dentry feature. |
6b4afdd7 JK |
136 | flush_merge Merge concurrent cache_flush commands as much as possible |
137 | to eliminate redundant command issues. If the underlying | |
138 | device handles the cache_flush command relatively slowly, | |
139 | recommend to enable this option. | |
0f7b2abd JK |
140 | nobarrier This option can be used if underlying storage guarantees |
141 | its cached data should be written to the novolatile area. | |
142 | If this option is set, no cache_flush commands are issued | |
143 | but f2fs still guarantees the write ordering of all the | |
144 | data writes. | |
d5053a34 JK |
145 | fastboot This option is used when a system wants to reduce mount |
146 | time as much as possible, even though normal performance | |
147 | can be sacrificed. | |
89672159 CY |
148 | extent_cache Enable an extent cache based on rb-tree, it can cache |
149 | as many as extent which map between contiguous logical | |
150 | address and physical address per inode, resulting in | |
7daaea25 | 151 | increasing the cache hit ratio. Set by default. |
c1286ff4 | 152 | noextent_cache Disable an extent cache based on rb-tree explicitly, see |
7daaea25 | 153 | the above extent_cache mount option. |
75342797 WL |
154 | noinline_data Disable the inline data feature, inline data feature is |
155 | enabled by default. | |
c1286ff4 JK |
156 | data_flush Enable data flushing before checkpoint in order to |
157 | persist data of regular and symlink. | |
158 | mode=%s Control block allocation mode which supports "adaptive" | |
159 | and "lfs". In "lfs" mode, there should be no random | |
160 | writes towards main area. | |
7b214391 JK |
161 | io_bits=%u Set the bit size of write IO requests. It should be set |
162 | with "mode=lfs". | |
13f00235 JK |
163 | usrquota Enable plain user disk quota accounting. |
164 | grpquota Enable plain group disk quota accounting. | |
165 | prjquota Enable plain project quota accounting. | |
166 | usrjquota=<file> Appoint specified file and type during mount, so that quota | |
167 | grpjquota=<file> information can be properly updated during recovery flow, | |
168 | prjjquota=<file> <quota file>: must be in root directory; | |
169 | jqfmt=<quota type> <quota type>: [vfsold,vfsv0,vfsv1]. | |
170 | offusrjquota Turn off user journelled quota. | |
171 | offgrpjquota Turn off group journelled quota. | |
172 | offprjjquota Turn off project journelled quota. | |
173 | quota Enable plain user disk quota accounting. | |
174 | noquota Disable all plain disk quota option. | |
98e4da8c JK |
175 | |
176 | ================================================================================ | |
177 | DEBUGFS ENTRIES | |
178 | ================================================================================ | |
179 | ||
180 | /sys/kernel/debug/f2fs/ contains information about all the partitions mounted as | |
181 | f2fs. Each file shows the whole f2fs information. | |
182 | ||
183 | /sys/kernel/debug/f2fs/status includes: | |
184 | - major file system information managed by f2fs currently | |
185 | - average SIT information about whole segments | |
186 | - current memory footprint consumed by f2fs. | |
187 | ||
b59d0bae NJ |
188 | ================================================================================ |
189 | SYSFS ENTRIES | |
190 | ================================================================================ | |
191 | ||
192 | Information about mounted f2f2 file systems can be found in | |
193 | /sys/fs/f2fs. Each mounted filesystem will have a directory in | |
194 | /sys/fs/f2fs based on its device name (i.e., /sys/fs/f2fs/sda). | |
195 | The files in each per-device directory are shown in table below. | |
196 | ||
197 | Files in /sys/fs/f2fs/<devname> | |
198 | (see also Documentation/ABI/testing/sysfs-fs-f2fs) | |
199 | .............................................................................. | |
200 | File Content | |
201 | ||
202 | gc_max_sleep_time This tuning parameter controls the maximum sleep | |
203 | time for the garbage collection thread. Time is | |
204 | in milliseconds. | |
205 | ||
206 | gc_min_sleep_time This tuning parameter controls the minimum sleep | |
207 | time for the garbage collection thread. Time is | |
208 | in milliseconds. | |
209 | ||
210 | gc_no_gc_sleep_time This tuning parameter controls the default sleep | |
211 | time for the garbage collection thread. Time is | |
212 | in milliseconds. | |
213 | ||
d2dc095f NJ |
214 | gc_idle This parameter controls the selection of victim |
215 | policy for garbage collection. Setting gc_idle = 0 | |
216 | (default) will disable this option. Setting | |
217 | gc_idle = 1 will select the Cost Benefit approach | |
c1286ff4 | 218 | & setting gc_idle = 2 will select the greedy approach. |
d2dc095f | 219 | |
13f00235 JK |
220 | gc_urgent This parameter controls triggering background GCs |
221 | urgently or not. Setting gc_urgent = 0 [default] | |
222 | makes back to default behavior, while if it is set | |
223 | to 1, background thread starts to do GC by given | |
224 | gc_urgent_sleep_time interval. | |
225 | ||
226 | gc_urgent_sleep_time This parameter controls sleep time for gc_urgent. | |
227 | 500 ms is set by default. See above gc_urgent. | |
228 | ||
ea91e9b0 JK |
229 | reclaim_segments This parameter controls the number of prefree |
230 | segments to be reclaimed. If the number of prefree | |
58c41035 JK |
231 | segments is larger than the number of segments |
232 | in the proportion to the percentage over total | |
233 | volume size, f2fs tries to conduct checkpoint to | |
234 | reclaim the prefree segments to free segments. | |
235 | By default, 5% over total # of segments. | |
ea91e9b0 | 236 | |
ba0697ec JK |
237 | max_small_discards This parameter controls the number of discard |
238 | commands that consist small blocks less than 2MB. | |
239 | The candidates to be discarded are cached until | |
240 | checkpoint is triggered, and issued during the | |
241 | checkpoint. By default, it is disabled with 0. | |
242 | ||
bba681cb JK |
243 | trim_sections This parameter controls the number of sections |
244 | to be trimmed out in batch mode when FITRIM | |
245 | conducts. 32 sections is set by default. | |
246 | ||
216fbd64 JK |
247 | ipu_policy This parameter controls the policy of in-place |
248 | updates in f2fs. There are five policies: | |
9b5f136f JK |
249 | 0x01: F2FS_IPU_FORCE, 0x02: F2FS_IPU_SSR, |
250 | 0x04: F2FS_IPU_UTIL, 0x08: F2FS_IPU_SSR_UTIL, | |
251 | 0x10: F2FS_IPU_FSYNC. | |
216fbd64 JK |
252 | |
253 | min_ipu_util This parameter controls the threshold to trigger | |
254 | in-place-updates. The number indicates percentage | |
255 | of the filesystem utilization, and used by | |
256 | F2FS_IPU_UTIL and F2FS_IPU_SSR_UTIL policies. | |
257 | ||
c1ce1b02 JK |
258 | min_fsync_blocks This parameter controls the threshold to trigger |
259 | in-place-updates when F2FS_IPU_FSYNC mode is set. | |
260 | The number indicates the number of dirty pages | |
261 | when fsync needs to flush on its call path. If | |
262 | the number is less than this value, it triggers | |
263 | in-place-updates. | |
264 | ||
3bac380c JK |
265 | max_victim_search This parameter controls the number of trials to |
266 | find a victim segment when conducting SSR and | |
267 | cleaning operations. The default value is 4096 | |
268 | which covers 8GB block address range. | |
269 | ||
ab9fa662 JK |
270 | dir_level This parameter controls the directory level to |
271 | support large directory. If a directory has a | |
272 | number of files, it can reduce the file lookup | |
273 | latency by increasing this dir_level value. | |
274 | Otherwise, it needs to decrease this value to | |
275 | reduce the space overhead. The default value is 0. | |
276 | ||
cdfc41c1 JK |
277 | ram_thresh This parameter controls the memory footprint used |
278 | by free nids and cached nat entries. By default, | |
279 | 10 is set, which indicates 10 MB / 1 GB RAM. | |
280 | ||
98e4da8c JK |
281 | ================================================================================ |
282 | USAGE | |
283 | ================================================================================ | |
284 | ||
285 | 1. Download userland tools and compile them. | |
286 | ||
287 | 2. Skip, if f2fs was compiled statically inside kernel. | |
288 | Otherwise, insert the f2fs.ko module. | |
289 | # insmod f2fs.ko | |
290 | ||
291 | 3. Create a directory trying to mount | |
292 | # mkdir /mnt/f2fs | |
293 | ||
294 | 4. Format the block device, and then mount as f2fs | |
295 | # mkfs.f2fs -l label /dev/block_device | |
296 | # mount -t f2fs /dev/block_device /mnt/f2fs | |
297 | ||
d51a7fba CL |
298 | mkfs.f2fs |
299 | --------- | |
300 | The mkfs.f2fs is for the use of formatting a partition as the f2fs filesystem, | |
301 | which builds a basic on-disk layout. | |
302 | ||
303 | The options consist of: | |
1571f84a | 304 | -l [label] : Give a volume label, up to 512 unicode name. |
98e4da8c JK |
305 | -a [0 or 1] : Split start location of each area for heap-based allocation. |
306 | 1 is set by default, which performs this. | |
307 | -o [int] : Set overprovision ratio in percent over volume size. | |
308 | 5 is set by default. | |
309 | -s [int] : Set the number of segments per section. | |
310 | 1 is set by default. | |
311 | -z [int] : Set the number of sections per zone. | |
312 | 1 is set by default. | |
313 | -e [str] : Set basic extension list. e.g. "mp3,gif,mov" | |
1571f84a CL |
314 | -t [0 or 1] : Disable discard command or not. |
315 | 1 is set by default, which conducts discard. | |
98e4da8c | 316 | |
d51a7fba CL |
317 | fsck.f2fs |
318 | --------- | |
319 | The fsck.f2fs is a tool to check the consistency of an f2fs-formatted | |
320 | partition, which examines whether the filesystem metadata and user-made data | |
321 | are cross-referenced correctly or not. | |
322 | Note that, initial version of the tool does not fix any inconsistency. | |
323 | ||
324 | The options consist of: | |
325 | -d debug level [default:0] | |
326 | ||
327 | dump.f2fs | |
328 | --------- | |
329 | The dump.f2fs shows the information of specific inode and dumps SSA and SIT to | |
330 | file. Each file is dump_ssa and dump_sit. | |
331 | ||
332 | The dump.f2fs is used to debug on-disk data structures of the f2fs filesystem. | |
c1286ff4 | 333 | It shows on-disk inode information recognized by a given inode number, and is |
d51a7fba CL |
334 | able to dump all the SSA and SIT entries into predefined files, ./dump_ssa and |
335 | ./dump_sit respectively. | |
336 | ||
337 | The options consist of: | |
338 | -d debug level [default:0] | |
339 | -i inode no (hex) | |
340 | -s [SIT dump segno from #1~#2 (decimal), for all 0~-1] | |
341 | -a [SSA dump segno from #1~#2 (decimal), for all 0~-1] | |
342 | ||
343 | Examples: | |
344 | # dump.f2fs -i [ino] /dev/sdx | |
345 | # dump.f2fs -s 0~-1 /dev/sdx (SIT dump) | |
346 | # dump.f2fs -a 0~-1 /dev/sdx (SSA dump) | |
347 | ||
98e4da8c JK |
348 | ================================================================================ |
349 | DESIGN | |
350 | ================================================================================ | |
351 | ||
352 | On-disk Layout | |
353 | -------------- | |
354 | ||
355 | F2FS divides the whole volume into a number of segments, each of which is fixed | |
356 | to 2MB in size. A section is composed of consecutive segments, and a zone | |
357 | consists of a set of sections. By default, section and zone sizes are set to one | |
358 | segment size identically, but users can easily modify the sizes by mkfs. | |
359 | ||
360 | F2FS splits the entire volume into six areas, and all the areas except superblock | |
361 | consists of multiple segments as described below. | |
362 | ||
363 | align with the zone size <-| | |
364 | |-> align with the segment size | |
365 | _________________________________________________________________________ | |
9268cc35 HL |
366 | | | | Segment | Node | Segment | | |
367 | | Superblock | Checkpoint | Info. | Address | Summary | Main | | |
368 | | (SB) | (CP) | Table (SIT) | Table (NAT) | Area (SSA) | | | |
98e4da8c JK |
369 | |____________|_____2______|______N______|______N______|______N_____|__N___| |
370 | . . | |
371 | . . | |
372 | . . | |
373 | ._________________________________________. | |
374 | |_Segment_|_..._|_Segment_|_..._|_Segment_| | |
375 | . . | |
376 | ._________._________ | |
377 | |_section_|__...__|_ | |
378 | . . | |
379 | .________. | |
380 | |__zone__| | |
381 | ||
382 | - Superblock (SB) | |
383 | : It is located at the beginning of the partition, and there exist two copies | |
384 | to avoid file system crash. It contains basic partition information and some | |
385 | default parameters of f2fs. | |
386 | ||
387 | - Checkpoint (CP) | |
388 | : It contains file system information, bitmaps for valid NAT/SIT sets, orphan | |
389 | inode lists, and summary entries of current active segments. | |
390 | ||
98e4da8c JK |
391 | - Segment Information Table (SIT) |
392 | : It contains segment information such as valid block count and bitmap for the | |
393 | validity of all the blocks. | |
394 | ||
9268cc35 HL |
395 | - Node Address Table (NAT) |
396 | : It is composed of a block address table for all the node blocks stored in | |
397 | Main area. | |
398 | ||
98e4da8c JK |
399 | - Segment Summary Area (SSA) |
400 | : It contains summary entries which contains the owner information of all the | |
401 | data and node blocks stored in Main area. | |
402 | ||
403 | - Main Area | |
404 | : It contains file and directory data including their indices. | |
405 | ||
406 | In order to avoid misalignment between file system and flash-based storage, F2FS | |
407 | aligns the start block address of CP with the segment size. Also, it aligns the | |
408 | start block address of Main area with the zone size by reserving some segments | |
409 | in SSA area. | |
410 | ||
411 | Reference the following survey for additional technical details. | |
412 | https://wiki.linaro.org/WorkingGroups/Kernel/Projects/FlashCardSurvey | |
413 | ||
414 | File System Metadata Structure | |
415 | ------------------------------ | |
416 | ||
417 | F2FS adopts the checkpointing scheme to maintain file system consistency. At | |
418 | mount time, F2FS first tries to find the last valid checkpoint data by scanning | |
419 | CP area. In order to reduce the scanning time, F2FS uses only two copies of CP. | |
420 | One of them always indicates the last valid data, which is called as shadow copy | |
421 | mechanism. In addition to CP, NAT and SIT also adopt the shadow copy mechanism. | |
422 | ||
423 | For file system consistency, each CP points to which NAT and SIT copies are | |
424 | valid, as shown as below. | |
425 | ||
426 | +--------+----------+---------+ | |
9268cc35 | 427 | | CP | SIT | NAT | |
98e4da8c JK |
428 | +--------+----------+---------+ |
429 | . . . . | |
430 | . . . . | |
431 | . . . . | |
432 | +-------+-------+--------+--------+--------+--------+ | |
9268cc35 | 433 | | CP #0 | CP #1 | SIT #0 | SIT #1 | NAT #0 | NAT #1 | |
98e4da8c JK |
434 | +-------+-------+--------+--------+--------+--------+ |
435 | | ^ ^ | |
436 | | | | | |
437 | `----------------------------------------' | |
438 | ||
439 | Index Structure | |
440 | --------------- | |
441 | ||
442 | The key data structure to manage the data locations is a "node". Similar to | |
443 | traditional file structures, F2FS has three types of node: inode, direct node, | |
d08ab08d | 444 | indirect node. F2FS assigns 4KB to an inode block which contains 923 data block |
98e4da8c JK |
445 | indices, two direct node pointers, two indirect node pointers, and one double |
446 | indirect node pointer as described below. One direct node block contains 1018 | |
447 | data blocks, and one indirect node block contains also 1018 node blocks. Thus, | |
448 | one inode block (i.e., a file) covers: | |
449 | ||
450 | 4KB * (923 + 2 * 1018 + 2 * 1018 * 1018 + 1018 * 1018 * 1018) := 3.94TB. | |
451 | ||
452 | Inode block (4KB) | |
453 | |- data (923) | |
454 | |- direct node (2) | |
455 | | `- data (1018) | |
456 | |- indirect node (2) | |
457 | | `- direct node (1018) | |
458 | | `- data (1018) | |
459 | `- double indirect node (1) | |
460 | `- indirect node (1018) | |
461 | `- direct node (1018) | |
462 | `- data (1018) | |
463 | ||
464 | Note that, all the node blocks are mapped by NAT which means the location of | |
465 | each node is translated by the NAT table. In the consideration of the wandering | |
466 | tree problem, F2FS is able to cut off the propagation of node updates caused by | |
467 | leaf data writes. | |
468 | ||
469 | Directory Structure | |
470 | ------------------- | |
471 | ||
472 | A directory entry occupies 11 bytes, which consists of the following attributes. | |
473 | ||
474 | - hash hash value of the file name | |
475 | - ino inode number | |
476 | - len the length of file name | |
477 | - type file type such as directory, symlink, etc | |
478 | ||
479 | A dentry block consists of 214 dentry slots and file names. Therein a bitmap is | |
480 | used to represent whether each dentry is valid or not. A dentry block occupies | |
481 | 4KB with the following composition. | |
482 | ||
483 | Dentry Block(4 K) = bitmap (27 bytes) + reserved (3 bytes) + | |
484 | dentries(11 * 214 bytes) + file name (8 * 214 bytes) | |
485 | ||
486 | [Bucket] | |
487 | +--------------------------------+ | |
488 | |dentry block 1 | dentry block 2 | | |
489 | +--------------------------------+ | |
490 | . . | |
491 | . . | |
492 | . [Dentry Block Structure: 4KB] . | |
493 | +--------+----------+----------+------------+ | |
494 | | bitmap | reserved | dentries | file names | | |
495 | +--------+----------+----------+------------+ | |
496 | [Dentry Block: 4KB] . . | |
497 | . . | |
498 | . . | |
499 | +------+------+-----+------+ | |
500 | | hash | ino | len | type | | |
501 | +------+------+-----+------+ | |
502 | [Dentry Structure: 11 bytes] | |
503 | ||
504 | F2FS implements multi-level hash tables for directory structure. Each level has | |
505 | a hash table with dedicated number of hash buckets as shown below. Note that | |
506 | "A(2B)" means a bucket includes 2 data blocks. | |
507 | ||
508 | ---------------------- | |
509 | A : bucket | |
510 | B : block | |
511 | N : MAX_DIR_HASH_DEPTH | |
512 | ---------------------- | |
513 | ||
514 | level #0 | A(2B) | |
515 | | | |
516 | level #1 | A(2B) - A(2B) | |
517 | | | |
518 | level #2 | A(2B) - A(2B) - A(2B) - A(2B) | |
519 | . | . . . . | |
520 | level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B) | |
521 | . | . . . . | |
522 | level #N | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B) | |
523 | ||
524 | The number of blocks and buckets are determined by, | |
525 | ||
526 | ,- 2, if n < MAX_DIR_HASH_DEPTH / 2, | |
527 | # of blocks in level #n = | | |
528 | `- 4, Otherwise | |
529 | ||
bfec07d0 CY |
530 | ,- 2^(n + dir_level), |
531 | | if n + dir_level < MAX_DIR_HASH_DEPTH / 2, | |
98e4da8c | 532 | # of buckets in level #n = | |
bfec07d0 CY |
533 | `- 2^((MAX_DIR_HASH_DEPTH / 2) - 1), |
534 | Otherwise | |
98e4da8c JK |
535 | |
536 | When F2FS finds a file name in a directory, at first a hash value of the file | |
537 | name is calculated. Then, F2FS scans the hash table in level #0 to find the | |
538 | dentry consisting of the file name and its inode number. If not found, F2FS | |
539 | scans the next hash table in level #1. In this way, F2FS scans hash tables in | |
540 | each levels incrementally from 1 to N. In each levels F2FS needs to scan only | |
541 | one bucket determined by the following equation, which shows O(log(# of files)) | |
542 | complexity. | |
543 | ||
544 | bucket number to scan in level #n = (hash value) % (# of buckets in level #n) | |
545 | ||
546 | In the case of file creation, F2FS finds empty consecutive slots that cover the | |
547 | file name. F2FS searches the empty slots in the hash tables of whole levels from | |
548 | 1 to N in the same way as the lookup operation. | |
549 | ||
550 | The following figure shows an example of two cases holding children. | |
551 | --------------> Dir <-------------- | |
552 | | | | |
553 | child child | |
554 | ||
555 | child - child [hole] - child | |
556 | ||
557 | child - child - child [hole] - [hole] - child | |
558 | ||
559 | Case 1: Case 2: | |
560 | Number of children = 6, Number of children = 3, | |
561 | File size = 7 File size = 7 | |
562 | ||
563 | Default Block Allocation | |
564 | ------------------------ | |
565 | ||
566 | At runtime, F2FS manages six active logs inside "Main" area: Hot/Warm/Cold node | |
567 | and Hot/Warm/Cold data. | |
568 | ||
569 | - Hot node contains direct node blocks of directories. | |
570 | - Warm node contains direct node blocks except hot node blocks. | |
571 | - Cold node contains indirect node blocks | |
572 | - Hot data contains dentry blocks | |
573 | - Warm data contains data blocks except hot and cold data blocks | |
574 | - Cold data contains multimedia data or migrated data blocks | |
575 | ||
576 | LFS has two schemes for free space management: threaded log and copy-and-compac- | |
577 | tion. The copy-and-compaction scheme which is known as cleaning, is well-suited | |
578 | for devices showing very good sequential write performance, since free segments | |
579 | are served all the time for writing new data. However, it suffers from cleaning | |
580 | overhead under high utilization. Contrarily, the threaded log scheme suffers | |
581 | from random writes, but no cleaning process is needed. F2FS adopts a hybrid | |
582 | scheme where the copy-and-compaction scheme is adopted by default, but the | |
583 | policy is dynamically changed to the threaded log scheme according to the file | |
584 | system status. | |
585 | ||
586 | In order to align F2FS with underlying flash-based storage, F2FS allocates a | |
587 | segment in a unit of section. F2FS expects that the section size would be the | |
588 | same as the unit size of garbage collection in FTL. Furthermore, with respect | |
589 | to the mapping granularity in FTL, F2FS allocates each section of the active | |
590 | logs from different zones as much as possible, since FTL can write the data in | |
591 | the active logs into one allocation unit according to its mapping granularity. | |
592 | ||
593 | Cleaning process | |
594 | ---------------- | |
595 | ||
596 | F2FS does cleaning both on demand and in the background. On-demand cleaning is | |
597 | triggered when there are not enough free segments to serve VFS calls. Background | |
598 | cleaner is operated by a kernel thread, and triggers the cleaning job when the | |
599 | system is idle. | |
600 | ||
601 | F2FS supports two victim selection policies: greedy and cost-benefit algorithms. | |
602 | In the greedy algorithm, F2FS selects a victim segment having the smallest number | |
603 | of valid blocks. In the cost-benefit algorithm, F2FS selects a victim segment | |
604 | according to the segment age and the number of valid blocks in order to address | |
605 | log block thrashing problem in the greedy algorithm. F2FS adopts the greedy | |
606 | algorithm for on-demand cleaner, while background cleaner adopts cost-benefit | |
607 | algorithm. | |
608 | ||
609 | In order to identify whether the data in the victim segment are valid or not, | |
610 | F2FS manages a bitmap. Each bit represents the validity of a block, and the | |
611 | bitmap is composed of a bit stream covering whole blocks in main area. |