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 | ||
21 | The file system formatting tool, "mkfs.f2fs", is available from the following | |
22 | download page: http://sourceforge.net/projects/f2fs-tools/ | |
23 | ||
24 | ================================================================================ | |
25 | BACKGROUND AND DESIGN ISSUES | |
26 | ================================================================================ | |
27 | ||
28 | Log-structured File System (LFS) | |
29 | -------------------------------- | |
30 | "A log-structured file system writes all modifications to disk sequentially in | |
31 | a log-like structure, thereby speeding up both file writing and crash recovery. | |
32 | The log is the only structure on disk; it contains indexing information so that | |
33 | files can be read back from the log efficiently. In order to maintain large free | |
34 | areas on disk for fast writing, we divide the log into segments and use a | |
35 | segment cleaner to compress the live information from heavily fragmented | |
36 | segments." from Rosenblum, M. and Ousterhout, J. K., 1992, "The design and | |
37 | implementation of a log-structured file system", ACM Trans. Computer Systems | |
38 | 10, 1, 26–52. | |
39 | ||
40 | Wandering Tree Problem | |
41 | ---------------------- | |
42 | In LFS, when a file data is updated and written to the end of log, its direct | |
43 | pointer block is updated due to the changed location. Then the indirect pointer | |
44 | block is also updated due to the direct pointer block update. In this manner, | |
45 | the upper index structures such as inode, inode map, and checkpoint block are | |
46 | also updated recursively. This problem is called as wandering tree problem [1], | |
47 | and in order to enhance the performance, it should eliminate or relax the update | |
48 | propagation as much as possible. | |
49 | ||
50 | [1] Bityutskiy, A. 2005. JFFS3 design issues. http://www.linux-mtd.infradead.org/ | |
51 | ||
52 | Cleaning Overhead | |
53 | ----------------- | |
54 | Since LFS is based on out-of-place writes, it produces so many obsolete blocks | |
55 | scattered across the whole storage. In order to serve new empty log space, it | |
56 | needs to reclaim these obsolete blocks seamlessly to users. This job is called | |
57 | as a cleaning process. | |
58 | ||
59 | The process consists of three operations as follows. | |
60 | 1. A victim segment is selected through referencing segment usage table. | |
61 | 2. It loads parent index structures of all the data in the victim identified by | |
62 | segment summary blocks. | |
63 | 3. It checks the cross-reference between the data and its parent index structure. | |
64 | 4. It moves valid data selectively. | |
65 | ||
66 | This cleaning job may cause unexpected long delays, so the most important goal | |
67 | is to hide the latencies to users. And also definitely, it should reduce the | |
68 | amount of valid data to be moved, and move them quickly as well. | |
69 | ||
70 | ================================================================================ | |
71 | KEY FEATURES | |
72 | ================================================================================ | |
73 | ||
74 | Flash Awareness | |
75 | --------------- | |
76 | - Enlarge the random write area for better performance, but provide the high | |
77 | spatial locality | |
78 | - Align FS data structures to the operational units in FTL as best efforts | |
79 | ||
80 | Wandering Tree Problem | |
81 | ---------------------- | |
82 | - Use a term, “node”, that represents inodes as well as various pointer blocks | |
83 | - Introduce Node Address Table (NAT) containing the locations of all the “node” | |
84 | blocks; this will cut off the update propagation. | |
85 | ||
86 | Cleaning Overhead | |
87 | ----------------- | |
88 | - Support a background cleaning process | |
89 | - Support greedy and cost-benefit algorithms for victim selection policies | |
90 | - Support multi-head logs for static/dynamic hot and cold data separation | |
91 | - Introduce adaptive logging for efficient block allocation | |
92 | ||
93 | ================================================================================ | |
94 | MOUNT OPTIONS | |
95 | ================================================================================ | |
96 | ||
97 | background_gc_off Turn off cleaning operations, namely garbage collection, | |
98 | triggered in background when I/O subsystem is idle. | |
99 | disable_roll_forward Disable the roll-forward recovery routine | |
100 | discard Issue discard/TRIM commands when a segment is cleaned. | |
101 | no_heap Disable heap-style segment allocation which finds free | |
102 | segments for data from the beginning of main area, while | |
103 | for node from the end of main area. | |
104 | nouser_xattr Disable Extended User Attributes. Note: xattr is enabled | |
105 | by default if CONFIG_F2FS_FS_XATTR is selected. | |
106 | noacl Disable POSIX Access Control List. Note: acl is enabled | |
107 | by default if CONFIG_F2FS_FS_POSIX_ACL is selected. | |
108 | active_logs=%u Support configuring the number of active logs. In the | |
109 | current design, f2fs supports only 2, 4, and 6 logs. | |
110 | Default number is 6. | |
111 | disable_ext_identify Disable the extension list configured by mkfs, so f2fs | |
112 | does not aware of cold files such as media files. | |
113 | ||
114 | ================================================================================ | |
115 | DEBUGFS ENTRIES | |
116 | ================================================================================ | |
117 | ||
118 | /sys/kernel/debug/f2fs/ contains information about all the partitions mounted as | |
119 | f2fs. Each file shows the whole f2fs information. | |
120 | ||
121 | /sys/kernel/debug/f2fs/status includes: | |
122 | - major file system information managed by f2fs currently | |
123 | - average SIT information about whole segments | |
124 | - current memory footprint consumed by f2fs. | |
125 | ||
126 | ================================================================================ | |
127 | USAGE | |
128 | ================================================================================ | |
129 | ||
130 | 1. Download userland tools and compile them. | |
131 | ||
132 | 2. Skip, if f2fs was compiled statically inside kernel. | |
133 | Otherwise, insert the f2fs.ko module. | |
134 | # insmod f2fs.ko | |
135 | ||
136 | 3. Create a directory trying to mount | |
137 | # mkdir /mnt/f2fs | |
138 | ||
139 | 4. Format the block device, and then mount as f2fs | |
140 | # mkfs.f2fs -l label /dev/block_device | |
141 | # mount -t f2fs /dev/block_device /mnt/f2fs | |
142 | ||
143 | Format options | |
144 | -------------- | |
145 | -l [label] : Give a volume label, up to 256 unicode name. | |
146 | -a [0 or 1] : Split start location of each area for heap-based allocation. | |
147 | 1 is set by default, which performs this. | |
148 | -o [int] : Set overprovision ratio in percent over volume size. | |
149 | 5 is set by default. | |
150 | -s [int] : Set the number of segments per section. | |
151 | 1 is set by default. | |
152 | -z [int] : Set the number of sections per zone. | |
153 | 1 is set by default. | |
154 | -e [str] : Set basic extension list. e.g. "mp3,gif,mov" | |
155 | ||
156 | ================================================================================ | |
157 | DESIGN | |
158 | ================================================================================ | |
159 | ||
160 | On-disk Layout | |
161 | -------------- | |
162 | ||
163 | F2FS divides the whole volume into a number of segments, each of which is fixed | |
164 | to 2MB in size. A section is composed of consecutive segments, and a zone | |
165 | consists of a set of sections. By default, section and zone sizes are set to one | |
166 | segment size identically, but users can easily modify the sizes by mkfs. | |
167 | ||
168 | F2FS splits the entire volume into six areas, and all the areas except superblock | |
169 | consists of multiple segments as described below. | |
170 | ||
171 | align with the zone size <-| | |
172 | |-> align with the segment size | |
173 | _________________________________________________________________________ | |
174 | | | | Node | Segment | Segment | | | |
175 | | Superblock | Checkpoint | Address | Info. | Summary | Main | | |
176 | | (SB) | (CP) | Table (NAT) | Table (SIT) | Area (SSA) | | | |
177 | |____________|_____2______|______N______|______N______|______N_____|__N___| | |
178 | . . | |
179 | . . | |
180 | . . | |
181 | ._________________________________________. | |
182 | |_Segment_|_..._|_Segment_|_..._|_Segment_| | |
183 | . . | |
184 | ._________._________ | |
185 | |_section_|__...__|_ | |
186 | . . | |
187 | .________. | |
188 | |__zone__| | |
189 | ||
190 | - Superblock (SB) | |
191 | : It is located at the beginning of the partition, and there exist two copies | |
192 | to avoid file system crash. It contains basic partition information and some | |
193 | default parameters of f2fs. | |
194 | ||
195 | - Checkpoint (CP) | |
196 | : It contains file system information, bitmaps for valid NAT/SIT sets, orphan | |
197 | inode lists, and summary entries of current active segments. | |
198 | ||
199 | - Node Address Table (NAT) | |
200 | : It is composed of a block address table for all the node blocks stored in | |
201 | Main area. | |
202 | ||
203 | - Segment Information Table (SIT) | |
204 | : It contains segment information such as valid block count and bitmap for the | |
205 | validity of all the blocks. | |
206 | ||
207 | - Segment Summary Area (SSA) | |
208 | : It contains summary entries which contains the owner information of all the | |
209 | data and node blocks stored in Main area. | |
210 | ||
211 | - Main Area | |
212 | : It contains file and directory data including their indices. | |
213 | ||
214 | In order to avoid misalignment between file system and flash-based storage, F2FS | |
215 | aligns the start block address of CP with the segment size. Also, it aligns the | |
216 | start block address of Main area with the zone size by reserving some segments | |
217 | in SSA area. | |
218 | ||
219 | Reference the following survey for additional technical details. | |
220 | https://wiki.linaro.org/WorkingGroups/Kernel/Projects/FlashCardSurvey | |
221 | ||
222 | File System Metadata Structure | |
223 | ------------------------------ | |
224 | ||
225 | F2FS adopts the checkpointing scheme to maintain file system consistency. At | |
226 | mount time, F2FS first tries to find the last valid checkpoint data by scanning | |
227 | CP area. In order to reduce the scanning time, F2FS uses only two copies of CP. | |
228 | One of them always indicates the last valid data, which is called as shadow copy | |
229 | mechanism. In addition to CP, NAT and SIT also adopt the shadow copy mechanism. | |
230 | ||
231 | For file system consistency, each CP points to which NAT and SIT copies are | |
232 | valid, as shown as below. | |
233 | ||
234 | +--------+----------+---------+ | |
235 | | CP | NAT | SIT | | |
236 | +--------+----------+---------+ | |
237 | . . . . | |
238 | . . . . | |
239 | . . . . | |
240 | +-------+-------+--------+--------+--------+--------+ | |
241 | | CP #0 | CP #1 | NAT #0 | NAT #1 | SIT #0 | SIT #1 | | |
242 | +-------+-------+--------+--------+--------+--------+ | |
243 | | ^ ^ | |
244 | | | | | |
245 | `----------------------------------------' | |
246 | ||
247 | Index Structure | |
248 | --------------- | |
249 | ||
250 | The key data structure to manage the data locations is a "node". Similar to | |
251 | traditional file structures, F2FS has three types of node: inode, direct node, | |
252 | indirect node. F2FS assigns 4KB to an inode block which contains 929 data block | |
253 | indices, two direct node pointers, two indirect node pointers, and one double | |
254 | indirect node pointer as described below. One direct node block contains 1018 | |
255 | data blocks, and one indirect node block contains also 1018 node blocks. Thus, | |
256 | one inode block (i.e., a file) covers: | |
257 | ||
258 | 4KB * (923 + 2 * 1018 + 2 * 1018 * 1018 + 1018 * 1018 * 1018) := 3.94TB. | |
259 | ||
260 | Inode block (4KB) | |
261 | |- data (923) | |
262 | |- direct node (2) | |
263 | | `- data (1018) | |
264 | |- indirect node (2) | |
265 | | `- direct node (1018) | |
266 | | `- data (1018) | |
267 | `- double indirect node (1) | |
268 | `- indirect node (1018) | |
269 | `- direct node (1018) | |
270 | `- data (1018) | |
271 | ||
272 | Note that, all the node blocks are mapped by NAT which means the location of | |
273 | each node is translated by the NAT table. In the consideration of the wandering | |
274 | tree problem, F2FS is able to cut off the propagation of node updates caused by | |
275 | leaf data writes. | |
276 | ||
277 | Directory Structure | |
278 | ------------------- | |
279 | ||
280 | A directory entry occupies 11 bytes, which consists of the following attributes. | |
281 | ||
282 | - hash hash value of the file name | |
283 | - ino inode number | |
284 | - len the length of file name | |
285 | - type file type such as directory, symlink, etc | |
286 | ||
287 | A dentry block consists of 214 dentry slots and file names. Therein a bitmap is | |
288 | used to represent whether each dentry is valid or not. A dentry block occupies | |
289 | 4KB with the following composition. | |
290 | ||
291 | Dentry Block(4 K) = bitmap (27 bytes) + reserved (3 bytes) + | |
292 | dentries(11 * 214 bytes) + file name (8 * 214 bytes) | |
293 | ||
294 | [Bucket] | |
295 | +--------------------------------+ | |
296 | |dentry block 1 | dentry block 2 | | |
297 | +--------------------------------+ | |
298 | . . | |
299 | . . | |
300 | . [Dentry Block Structure: 4KB] . | |
301 | +--------+----------+----------+------------+ | |
302 | | bitmap | reserved | dentries | file names | | |
303 | +--------+----------+----------+------------+ | |
304 | [Dentry Block: 4KB] . . | |
305 | . . | |
306 | . . | |
307 | +------+------+-----+------+ | |
308 | | hash | ino | len | type | | |
309 | +------+------+-----+------+ | |
310 | [Dentry Structure: 11 bytes] | |
311 | ||
312 | F2FS implements multi-level hash tables for directory structure. Each level has | |
313 | a hash table with dedicated number of hash buckets as shown below. Note that | |
314 | "A(2B)" means a bucket includes 2 data blocks. | |
315 | ||
316 | ---------------------- | |
317 | A : bucket | |
318 | B : block | |
319 | N : MAX_DIR_HASH_DEPTH | |
320 | ---------------------- | |
321 | ||
322 | level #0 | A(2B) | |
323 | | | |
324 | level #1 | A(2B) - A(2B) | |
325 | | | |
326 | level #2 | A(2B) - A(2B) - A(2B) - A(2B) | |
327 | . | . . . . | |
328 | level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B) | |
329 | . | . . . . | |
330 | level #N | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B) | |
331 | ||
332 | The number of blocks and buckets are determined by, | |
333 | ||
334 | ,- 2, if n < MAX_DIR_HASH_DEPTH / 2, | |
335 | # of blocks in level #n = | | |
336 | `- 4, Otherwise | |
337 | ||
338 | ,- 2^n, if n < MAX_DIR_HASH_DEPTH / 2, | |
339 | # of buckets in level #n = | | |
340 | `- 2^((MAX_DIR_HASH_DEPTH / 2) - 1), Otherwise | |
341 | ||
342 | When F2FS finds a file name in a directory, at first a hash value of the file | |
343 | name is calculated. Then, F2FS scans the hash table in level #0 to find the | |
344 | dentry consisting of the file name and its inode number. If not found, F2FS | |
345 | scans the next hash table in level #1. In this way, F2FS scans hash tables in | |
346 | each levels incrementally from 1 to N. In each levels F2FS needs to scan only | |
347 | one bucket determined by the following equation, which shows O(log(# of files)) | |
348 | complexity. | |
349 | ||
350 | bucket number to scan in level #n = (hash value) % (# of buckets in level #n) | |
351 | ||
352 | In the case of file creation, F2FS finds empty consecutive slots that cover the | |
353 | file name. F2FS searches the empty slots in the hash tables of whole levels from | |
354 | 1 to N in the same way as the lookup operation. | |
355 | ||
356 | The following figure shows an example of two cases holding children. | |
357 | --------------> Dir <-------------- | |
358 | | | | |
359 | child child | |
360 | ||
361 | child - child [hole] - child | |
362 | ||
363 | child - child - child [hole] - [hole] - child | |
364 | ||
365 | Case 1: Case 2: | |
366 | Number of children = 6, Number of children = 3, | |
367 | File size = 7 File size = 7 | |
368 | ||
369 | Default Block Allocation | |
370 | ------------------------ | |
371 | ||
372 | At runtime, F2FS manages six active logs inside "Main" area: Hot/Warm/Cold node | |
373 | and Hot/Warm/Cold data. | |
374 | ||
375 | - Hot node contains direct node blocks of directories. | |
376 | - Warm node contains direct node blocks except hot node blocks. | |
377 | - Cold node contains indirect node blocks | |
378 | - Hot data contains dentry blocks | |
379 | - Warm data contains data blocks except hot and cold data blocks | |
380 | - Cold data contains multimedia data or migrated data blocks | |
381 | ||
382 | LFS has two schemes for free space management: threaded log and copy-and-compac- | |
383 | tion. The copy-and-compaction scheme which is known as cleaning, is well-suited | |
384 | for devices showing very good sequential write performance, since free segments | |
385 | are served all the time for writing new data. However, it suffers from cleaning | |
386 | overhead under high utilization. Contrarily, the threaded log scheme suffers | |
387 | from random writes, but no cleaning process is needed. F2FS adopts a hybrid | |
388 | scheme where the copy-and-compaction scheme is adopted by default, but the | |
389 | policy is dynamically changed to the threaded log scheme according to the file | |
390 | system status. | |
391 | ||
392 | In order to align F2FS with underlying flash-based storage, F2FS allocates a | |
393 | segment in a unit of section. F2FS expects that the section size would be the | |
394 | same as the unit size of garbage collection in FTL. Furthermore, with respect | |
395 | to the mapping granularity in FTL, F2FS allocates each section of the active | |
396 | logs from different zones as much as possible, since FTL can write the data in | |
397 | the active logs into one allocation unit according to its mapping granularity. | |
398 | ||
399 | Cleaning process | |
400 | ---------------- | |
401 | ||
402 | F2FS does cleaning both on demand and in the background. On-demand cleaning is | |
403 | triggered when there are not enough free segments to serve VFS calls. Background | |
404 | cleaner is operated by a kernel thread, and triggers the cleaning job when the | |
405 | system is idle. | |
406 | ||
407 | F2FS supports two victim selection policies: greedy and cost-benefit algorithms. | |
408 | In the greedy algorithm, F2FS selects a victim segment having the smallest number | |
409 | of valid blocks. In the cost-benefit algorithm, F2FS selects a victim segment | |
410 | according to the segment age and the number of valid blocks in order to address | |
411 | log block thrashing problem in the greedy algorithm. F2FS adopts the greedy | |
412 | algorithm for on-demand cleaner, while background cleaner adopts cost-benefit | |
413 | algorithm. | |
414 | ||
415 | In order to identify whether the data in the victim segment are valid or not, | |
416 | F2FS manages a bitmap. Each bit represents the validity of a block, and the | |
417 | bitmap is composed of a bit stream covering whole blocks in main area. |