From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jaegeuk Kim Subject: RE: [PATCH 01/16 v2] f2fs: add document Date: Fri, 26 Oct 2012 07:14:35 +0900 Message-ID: <00c001cdb2fe$1dad0cd0$59072670$%kim@samsung.com> References: <001001cdb0c5$2ac96520$805c2f60$%kim@samsung.com> <001101cdb0c5$a1052fd0$e30f8f70$%kim@samsung.com> <1350992475.2041.44.camel@slavad-ubuntu> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, gregkh@linuxfoundation.org, viro@zeniv.linux.org.uk, arnd@arndb.de, tytso@mit.edu, chur.lee@samsung.com, cm224.lee@samsung.com, jooyoung.hwang@samsung.com To: 'Vyacheslav Dubeyko' Return-path: In-reply-to: <1350992475.2041.44.camel@slavad-ubuntu> Content-language: en-us Sender: linux-kernel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org I'll enhance the document as much as possible according to your recommendation. Thank you for intensive review. :) --- Jaegeuk Kim Samsung > On Tue, 2012-10-23 at 11:25 +0900, Jaegeuk Kim wrote: > > This adds a document describing the mount options, proc entries, us= age, and > > design of Flash-Friendly File System, namely F2FS. > > > > Signed-off-by: Jaegeuk Kim > > --- > > Documentation/filesystems/00-INDEX | 2 + > > Documentation/filesystems/f2fs.txt | 404 ++++++++++++++++++++++++= ++++++++++++ > > 2 files changed, 406 insertions(+) > > create mode 100644 Documentation/filesystems/f2fs.txt > > > > diff --git a/Documentation/filesystems/00-INDEX b/Documentation/fil= esystems/00-INDEX > > index 8c624a1..ce5fd46 100644 > > --- a/Documentation/filesystems/00-INDEX > > +++ b/Documentation/filesystems/00-INDEX > > @@ -48,6 +48,8 @@ ext4.txt > > - info, mount options and specifications for the Ext4 filesystem. > > files.txt > > - info on file management in the Linux kernel. > > +f2fs.txt > > + - info and mount options for the F2FS filesystem. > > fuse.txt > > - info on the Filesystem in User SpacE including mount options. > > gfs2.txt > > diff --git a/Documentation/filesystems/f2fs.txt b/Documentation/fil= esystems/f2fs.txt > > new file mode 100644 > > index 0000000..f2b4fde > > --- /dev/null > > +++ b/Documentation/filesystems/f2fs.txt > > @@ -0,0 +1,404 @@ > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > +WHAT IS Flash-Friendly File System (F2FS)? > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > + > > +NAND flash memory-based storage devices, such as SSD, eMMC, and SD= cards, have > > +been widely being used for storage ranging from mobile to server s= ystems. Since >=20 > Maybe, it needs to reformulate "... have been widely being used ..."? >=20 > > +they are known to have different characteristics from the conventi= onal rotating > > +disks, a file system, an upper layer to the storage device, should= adapt to the > > +changes from the sketch in the design level. > > + > > +F2FS is a file system exploiting NAND flash memory-based storage d= evices, which > > +is based on Log-structured File System (LFS). The design has been = focused on > > +addressing the fundamental issues in LFS, which are snowball effec= t of wandering > > +tree and high cleaning overhead. > > + > > +Since a NAND flash memory-based storage device shows different cha= racteristic > > +according to its internal geometry or flash memory management sche= me, namely FTL, > > +F2FS and its tools support various parameters not only for configu= ring on-disk > > +layout, but also for selecting allocation and cleaning algorithms. > > + > > +The file system formatting tool, "mkfs.f2fs", is available from th= e following > > +download page: http://sourceforge.net/projects/f2fs-tools/ > > + > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > +BACKGROUND AND DESIGN ISSUES > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > + > > +Log-structured File System (LFS) > > +-------------------------------- > > +"A log-structured file system writes all modifications to disk seq= uentially in > > +a log-like structure, thereby speeding up both file writing and c= rash recovery. > > +The log is the only structure on disk; it contains indexing inform= ation so that > > +files can be read back from the log efficiently. In order to maint= ain large free > > +areas on disk for fast writing, we divide the log into segments a= nd use a > > +segment cleaner to compress the live information from heavily frag= mented > > +segments." from Rosenblum, M. and Ousterhout, J. K., 1992, "The de= sign and > > +implementation of a log-structured file system", ACM Trans. Comput= er Systems > > +10, 1, 26=E2=80=9352. > > + > > +Wandering Tree Problem > > +---------------------- > > +In LFS, when a file data is updated and written to the end of log,= its direct > > +pointer block is updated due to the changed location. Then the ind= irect pointer > > +block is also updated due to the direct pointer block update. In t= his manner, > > +the upper index structures such as inode, inode map, and checkpoin= t block are > > +also updated recursively. This problem is called as wandering tree= problem [1], > > +and in order to enhance the performance, it should eliminate or re= lax the update > > +propagation as much as possible. > > + > > +[1] Bityutskiy, A. 2005. JFFS3 design issues. http://www.linux-mtd= =2Einfradead.org/ > > + > > +Cleaning Overhead > > +----------------- > > +Since LFS is based on out-of-place writes, it produces so many obs= olete blocks > > +scattered across the whole storage. In order to serve new empty lo= g space, it > > +needs to reclaim these obsolete blocks seamlessly to users. This j= ob is called > > +as a cleaning process. > > + > > +The process consists of three operations as follows. > > +1. A victim segment is selected through referencing segment usage = table. > > +2. It loads parent index structures of all the data in the victim = identified by > > + segment summary blocks. > > +3. It checks the cross-reference between the data and its parent i= ndex structure. > > +4. It moves valid data selectively. > > + > > +This cleaning job may cause unexpected long delays, so the most im= portant goal > > +is to hide the latencies to users. And also definitely, it should = reduce the > > +amount of valid data to be moved, and move them quickly as well. > > + > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > +KEY FEATURES > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > + > > +Flash Awareness > > +--------------- > > +- Enlarge the random write area for better performance, but provid= e the high > > + spatial locality > > +- Align FS data structures to the operational units in FTL as best= efforts > > + > > +Wandering Tree Problem > > +---------------------- > > +- Use a term, =E2=80=9Cnode=E2=80=9D, that represents inodes as we= ll as various pointer blocks > > +- Introduce Node Address Table (NAT) containing the locations of a= ll the =E2=80=9Cnode=E2=80=9D > > + blocks; this will cut off the update propagation. > > + > > +Cleaning Overhead > > +----------------- > > +- Support a background cleaning process > > +- Support greedy and cost-benefit algorithms for victim selection = policies > > +- Support multi-head logs for static/dynamic hot and cold data sep= aration > > +- Introduce adaptive logging for efficient block allocation > > + > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > +MOUNT OPTIONS > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > + > > +background_gc_off Turn off cleaning operations, namely garbag= e collection, > > + triggered in background when I/O subsystem is idle. > > +disable_roll_forward Disable the roll-forward recovery routine > > +discard Issue discard/TRIM commands when a segment = is cleaned. > > +no_heap Disable heap-style segment allocation which= finds free > > + segments for data from the beginning of mai= n area, while > > + for node from the end of main area. > > +nouser_xattr Disable Extended User Attributes. Note: xat= tr is enabled > > + by default if CONFIG_F2FS_FS_XATTR is selec= ted. > > +noacl Disable POSIX Access Control List. Note: ac= l is enabled > > + by default if CONFIG_F2FS_FS_POSIX_ACL is s= elected. > > +active_logs=3D%u Support configuring the number of active = logs. In the > > + current design, f2fs supports only 2, 4, an= d 6 logs. > > + Default number is 6. > > +disable_ext_identify Disable the extension list configured by mk= fs, so f2fs > > + does not aware of cold files such as media = files. > > + > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > +PROC ENTRIES > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > + > > +/proc/fs/f2fs/ contains information about partitions mounted as f2= fs. For each > > +partition, a corresponding directory, named as its device name, is= provided with > > +the following proc entries. > > + > > +- f2fs_stat major file system information managed by f2fs currentl= y > > +- f2fs_sit_stat average utilization information of the whole segme= nts > > +- f2fs_mem_stat current memory footprint consumed by f2fs > > + > > +e.g., in /proc/fs/f2fs/sdb1/ > > + > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > +USAGE > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > + > > +1. Download userland tools > > + > > +2. Insmod f2fs.ko module: > > + # insmod f2fs.ko > > + >=20 > What about the case of static compilation of f2fs in the kernel? >=20 > > +3. Check the directory trying to mount > > + # mkdir /mnt/f2fs > > + >=20 > Create or check? >=20 > > +4. Format the block device, and then mount as f2fs > > + # mkfs.f2fs -l label /dev/block_device > > + # mount -t f2fs /dev/block_device /mnt/f2fs > > + > > +Mount options >=20 > Sorry, is it really mount options? Maybe, I misunderstand possibility= to > set volume label during mount. >=20 > > +------------- > > +-l [label] : Give a volume label, up to 256 unicode name. > > +-a [0 or 1] : Split start location of each area for heap-based al= location. > > + 1 is set by default, which performs this. > > +-o [int] : Set overprovision ratio in percent over volume size= =2E > > + 5 is set by default. > > +-s [int] : Set the number of segments per section. > > + 1 is set by default. > > +-z [int] : Set the number of sections per zone. > > + 1 is set by default. > > +-e [str] : Set basic extension list. e.g. "mp3,gif,mov" > > + > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > +DESIGN > > +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > + > > +On-disk Layout > > +-------------- > > + > > +F2FS divides the whole volume into a number of segments, each of w= hich is 2MB in > > +size by default. A section is composed of consecutive segments, an= d a zone > > +consists of a set of sections. > > + >=20 > Maybe, it makes sense to describe here possible sizes of sections and > zones? >=20 > > +F2FS maintains logically six log areas. Except SB, all the log are= as are managed > > +in a unit of multiple segments. SB is located at the beginning of = the partition, > > +and there exist two superblocks to avoid file system crash. Other = file system > > +metadata such as CP, NAT, SIT, and SSA are located in the front pa= rt of the > > +volume. Main area contains file and directory data including their= indices. > > + >=20 > I feel necessity to know more details about log concept here. Could y= ou > add slightly more description about log? >=20 > > +Each area manages the following contents. > > +- CP File system information, bitmaps for valid NAT/SIT sets, orp= han > > + inode lists, and summary entries of current active segments. > > +- NAT Block address table for all the node blocks stored in Main = area. > > +- SIT Segment information such as valid block count and bitmap fo= r the > > + validity of all the blocks. > > +- SSA Summary entries which contains the owner information of all= the > > + data and node blocks stored in Main area. > > +- Main Node and data blocks. > > + >=20 > Could you add definition of abbreviations here also (for example, NAT > Node Address Table: )? >=20 > > +In order to avoid misalignment between file system and flash-based= storage, F2FS > > +aligns the start block address of CP with the segment size. Also, = it aligns the > > +start block address of Main area with the zone size by reserving s= ome segments > > +in SSA area. >=20 > Maybe, it makes sense to add some technical details about aligning > procedure here? >=20 > > + > > + align with the zone si= ze <-| > > + |-> align with the segment size > > + _____________________________________________________________= ____________ > > + | | | Node | Segment | Segm= ent | | > > + | Superblock | Checkpoint | Address | Info. | Summ= ary | Main | > > + | (SB) | (CP) | Table (NAT) | Table (SIT) | Area (= SSA) | | > > + |____________|_____2______|______N______|______N______|______N= _____|__N___| > > + = . . > > + . = . > > + . = . > > + ._____________________________= ____________. > > + |_Segment_|_..._|_Segment_|_..= =2E_|_Segment_| > > + . . > > + ._________._________ > > + |_section_|__...__|_ > > + . . > > + .________. > > + |__zone__| > > + > > + > > +File System Metadata Structure > > +------------------------------ > > + > > +F2FS adopts the checkpointing scheme to maintain file system consi= stency. At > > +mount time, F2FS first tries to find the last valid checkpoint dat= a by scanning > > +CP area. In order to reduce the scanning time, F2FS uses only two = copies of CP. > > +One of them always indicates the last valid data, which is called = as shadow copy > > +mechanism. In addition to CP, NAT and SIT also adopt the shadow co= py mechanism. > > + > > +For file system consistency, each CP points to which NAT and SIT c= opies are > > +valid, as shown as below. > > + > > + +--------+----------+---------+ > > + | CP | NAT | SIT | > > + +--------+----------+---------+ > > + . . . . > > + . . . . > > + . . . . > > + +-------+-------+--------+--------+--------+--------+ > > + | CP #0 | CP #1 | NAT #0 | NAT #1 | SIT #0 | SIT #1 | > > + +-------+-------+--------+--------+--------+--------+ > > + | ^ ^ > > + | | | > > + `----------------------------------------' > > + > > +Index Structure > > +--------------- > > + > > +The key data structure to manage the data locations is a "node". S= imilar to > > +traditional file structures, F2FS has three types of node: inode, = direct node, > > +indirect node. F2FS assigns 4KB to an inode block which contains 9= 29 data block > > +indices, two direct node pointers, two indirect node pointers, and= one double > > +indirect node pointer as described below. One direct node block co= ntains 1018 > > +data blocks, and one indirect node block contains also 1018 node b= locks. Thus, > > +one inode block (i.e., a file) covers: > > + > > + 4KB * (927 + 2 * 1018 + 2 * 1018 * 1018 + 1018 * 1018 * 1018) :=3D= 3.94TB. > > + > > + Inode block (4KB) > > + |- data (927) > > + |- direct node (2) > > + | `- data (1018) > > + |- indirect node (2) > > + | `- direct node (1018) > > + | `- data (1018) > > + `- double indirect node (1) > > + `- indirect node (1018) > > + `- direct node (1018) > > + `- data (1018) > > + > > +Note that, all the node blocks are mapped by NAT which means the l= ocation of > > +each node is translated by the NAT table. In the consideration of = the wandering > > +tree problem, F2FS is able to cut off the propagation of node upda= tes caused by > > +leaf data writes. > > + > > +Directory Structure > > +------------------- > > + > > +A directory entry occupies 11 bytes, which consists of the followi= ng attributes. > > + > > +- hash hash value of the file name > > +- ino inode number > > +- len the length of file name > > +- type file type such as directory, symlink, etc > > + > > +A dentry block consists of 214 dentry slots and file names. Therei= n a bitmap is > > +used to represent whether each dentry is valid or not. A dentry bl= ock occupies > > +4KB with the following composition. > > + > > + Dentry Block(4 K) =3D bitmap (27 bytes) + reserved (3 bytes) + > > + dentries(11 * 214 bytes) + file name (8 * 214 bytes= ) > > + > > + [Bucket] > > + +--------------------------------+ > > + |dentry block 1 | dentry block 2 | > > + +--------------------------------+ > > + . . > > + . . > > + . [Dentry Block Structure: 4KB] . > > + +--------+----------+----------+------------+ > > + | bitmap | reserved | dentries | file names | > > + +--------+----------+----------+------------+ > > + [Dentry Block: 4KB] . . > > + . . > > + . . > > + +------+------+-----+------+ > > + | hash | ino | len | type | > > + +------+------+-----+------+ > > + [Dentry Structure: 11 bytes] > > + > > +F2FS implements multi-level hash tables for directory structure. E= ach level has > > +a hash table with dedicated number of hash buckets as shown below.= Note that > > +"A(2B)" means a bucket includes 2 data blocks. > > + > > +---------------------- > > +A : bucket > > +B : block > > +N : MAX_DIR_HASH_DEPTH > > +---------------------- > > + > > +level #0 | A(2B) > > + | > > +level #1 | A(2B) - A(2B) > > + | > > +level #2 | A(2B) - A(2B) - A(2B) - A(2B) > > + . | . . . . > > +level #N/2 | A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B) > > + . | . . . . > > +level #N | A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B) > > + > > +The number of blocks and buckets are determined by, > > + > > + ,- 2, if n < MAX_DIR_HASH_DEPTH / 2, > > + # of blocks in level #n =3D | > > + `- 4, Otherwise > > + > > + ,- 2^n, if n < MAX_DIR_HASH_DEPTH / 2= , > > + # of buckets in level #n =3D | > > + `- 2^((MAX_DIR_HASH_DEPTH / 2) - 1), = Otherwise > > + > > +When F2FS finds a file name in a directory, at first a hash value = of the file > > +name is calculated. Then, F2FS scans the hash table in level #0 to= find the > > +dentry consisting of the file name and its inode number. If not fo= und, F2FS > > +scans the next hash table in level #1. In this way, F2FS scans has= h tables in > > +each levels incrementally from 1 to N. In each levels F2FS needs t= o scan only > > +one bucket determined by the following equation, which shows O(log= (# of files)) > > +complexity. > > + > > + bucket number to scan in level #n =3D (hash value) % (# of bucke= ts in level #n) > > + > > +In the case of file creation, F2FS finds empty consecutive slots t= hat cover the > > +file name. F2FS searches the empty slots in the hash tables of who= le levels from > > +1 to N in the same way as the lookup operation. > > + > > +The following figure shows an example of two cases holding childre= n. > > + --------------> Dir <-------------- > > + | | > > + child child > > + > > + child - child [hole] - child > > + > > + child - child - child [hole] - [hole] - child > > + > > + Case 1: Case 2: > > + Number of children =3D 6, Number of children =3D 3, > > + File size =3D 7 File size =3D 7 > > + > > +Default Block Allocation > > +------------------------ > > + > > +At runtime, F2FS manages six active logs inside "Main" area: Hot/W= arm/Cold node > > +and Hot/Warm/Cold data. > > + > > +- Hot node contains direct node blocks of directories. > > +- Warm node contains direct node blocks except hot node blocks. > > +- Cold node contains indirect node blocks > > +- Hot data contains dentry blocks > > +- Warm data contains data blocks except hot and cold data blocks > > +- Cold data contains multimedia data or migrated data blocks > > + > > +LFS has two schemes for free space management: threaded log and co= py-and-compac- > > +tion. The copy-and-compaction scheme which is known as cleaning, i= s well-suited > > +for devices showing very good sequential write performance, since = free segments > > +are served all the time for writing new data. However, it suffers = from cleaning > > +overhead under high utilization. Contrarily, the threaded log sche= me suffers > > +from random writes, but no cleaning process is needed. F2FS adopts= a hybrid > > +scheme where the copy-and-compaction scheme is adopted by default,= but the > > +policy is dynamically changed to the threaded log scheme according= to the file > > +system status. > > + > > +In order to align F2FS with underlying flash-based storage, F2FS a= llocates a > > +segment in a unit of section. F2FS expects that the section size w= ould be the > > +same as the unit size of garbage collection in FTL. Furthermore, w= ith respect > > +to the mapping granularity in FTL, F2FS allocates each section of = the active > > +logs from different zones as much as possible, since FTL can write= the data in > > +the active logs into one allocation unit according to its mapping = granularity. > > + > > +Cleaning process > > +---------------- > > + > > +F2FS does cleaning both on demand and in the background. On-demand= cleaning is > > +triggered when there are not enough free segments to serve VFS cal= ls. Background > > +cleaner is operated by a kernel thread, and triggers the cleaning = job when the > > +system is idle. > > + > > +F2FS supports two victim selection policies: greedy and cost-benef= it algorithms. > > +In the greedy algorithm, F2FS selects a victim segment having the = smallest number > > +of valid blocks. In the cost-benefit algorithm, F2FS selects a vic= tim segment > > +according to the segment age and the number of valid blocks in ord= er to address > > +log block thrashing problem in the greedy algorithm. F2FS adopts t= he greedy > > +algorithm for on-demand cleaner, while background cleaner adopts c= ost-benefit > > +algorithm. > > + > > +In order to identify whether the data in the victim segment are va= lid or not, > > +F2FS manages a bitmap. Each bit represents the validity of a block= , and the > > +bitmap is composed of a bit stream covering whole blocks in main a= rea. >=20 > With the best regards, > Vyacheslav Dubeyko.