【文件系统】 F2FS文件系统学习

一、基本介绍

1、F2FS History

F2FS（Flash Friendly File System）是专门为Nand Flash设计的一个日志型文件系统，于2012年12月合入Linux3.8内核，Google也在2018年（Android P）将其吸收到安卓原生版本中，使所有使用安卓的厂商受益

2、F2FS特点

F2FS可以极大程度上避免碎片产生，相对于传统日志型文件系统，F2FS在wandering tree和gc方面，有一定的优化，可以复用离散的数据页写入数据，显著减少GC带来的卡顿

wandering tree：在文件更新时，指向文件的DIrect Pointer由于数据异地更新，也会随之更新，同时指向这个DIrect Pointer的Indirect Pointer也会更新，然后保存这个Indirect Pointer的inode、inode blockmap等结构也需要更新，这样会导致频繁的metadata更新

3、为什么需要F2FS

Nand Flash在更新某个位置的值时，必须先擦除，才能写入新的内容，如果在频繁写入的场景，都需要消耗大量的时间进行擦除，导致整体性能下降。F2FS基于LFS型文件系统，解决了先擦后写的问题，当需要更新某个块时，会重新申请一个未使用的快，将数据写到新的块上，并更新相应的管理数据，这样就避免等待block擦除的开销，并且可以将随机写转化为顺序写，提升性能

不仅仅是提升性能，对写放大也有所降低，这是因为如果按照先擦后写，就会导致某个块频繁被删除，导致写穿寿命到期，成为坏块，而F2FS使用append-only logging策略，按顺序写入数据，天然的在文件系统层做了磨损均衡，延长了设备使用寿命

此外，F2FS支持冷热Node/Data分流，将不经常变动的数据写入冷分区，将经常需要变动的数据写入到热分区，这样在器件回收数据块时，可以根据数据块的冷热进行选择，提高回收效率

二、F2FS 数据结构

1、F2FS Layout

F2FS磁盘布局如下图所示，它考虑了闪存感知和低清理成本

闪存感知：指文件系统匹配闪存物理特性

（a）superblock metadata放在一起，且是头部，提高局部性和并行性

（b）main area起始地址对对齐zoned大小，考虑了FTL工作特性

（c）以section为单位进行文件系统GC

低清理成本：使用Multi-Stream logging实现冷热数据分流

（a）F2FS将整个磁盘划分为若干segment，每个大小为2MB

（b）目前zone，section，segment都是1:1:1的关系，zone的大小与物理设备有关

（c）除superblock外，其他area都有多个segment

（d）1个segment包含512个block，1个block大小为4KB

(1) SuperBlock

该区域占一个segment（2MB），包含两个f2fs_super_block数据结构，每个占用4KB。

struct f2fs_super_block {
	__le32 magic;			/* Magic Number */
	__le16 major_ver;		/* Major Version */
	__le16 minor_ver;		/* Minor Version */
	__le32 log_sectorsize;		/* log2 sector size in bytes */
	__le32 log_sectors_per_block;	/* log2 # of sectors per block */
	__le32 log_blocksize;		/* log2 block size in bytes */
	__le32 log_blocks_per_seg;	/* log2 # of blocks per segment */
	__le32 segs_per_sec;		/* # of segments per section */
	__le32 secs_per_zone;		/* # of sections per zone */
	__le32 checksum_offset;		/* checksum offset inside super block */
	__le64 block_count;		/* total # of user blocks */
	__le32 section_count;		/* total # of sections */
	__le32 segment_count;		/* total # of segments */
	__le32 segment_count_ckpt;	/* # of segments for checkpoint */
	__le32 segment_count_sit;	/* # of segments for SIT */
	__le32 segment_count_nat;	/* # of segments for NAT */
	__le32 segment_count_ssa;	/* # of segments for SSA */
	__le32 segment_count_main;	/* # of segments for main area */
	__le32 segment0_blkaddr;	/* start block address of segment 0 */
	__le32 cp_blkaddr;		/* start block address of checkpoint */
	__le32 sit_blkaddr;		/* start block address of SIT */
	__le32 nat_blkaddr;		/* start block address of NAT */
	__le32 ssa_blkaddr;		/* start block address of SSA */
	__le32 main_blkaddr;		/* start block address of main area */
	__le32 root_ino;		/* root inode number */
	__le32 node_ino;		/* node inode number */
	__le32 meta_ino;		/* meta inode number */
	__u8 uuid[16];			/* 128-bit uuid for volume */
	__le16 volume_name[MAX_VOLUME_NAME];	/* volume name */
	__le32 extension_count;		/* # of extensions below */
	__u8 extension_list[F2FS_MAX_EXTENSION][F2FS_EXTENSION_LEN];/* extension array */
	__le32 cp_payload;
	__u8 version[VERSION_LEN];	/* the kernel version */
	__u8 init_version[VERSION_LEN];	/* the initial kernel version */
	__le32 feature;			/* defined features */
	__u8 encryption_level;		/* versioning level for encryption */
	__u8 encrypt_pw_salt[16];	/* Salt used for string2key algorithm */
	struct f2fs_device devs[MAX_DEVICES];	/* device list */
	__le32 qf_ino[F2FS_MAX_QUOTAS];	/* quota inode numbers */
	__u8 hot_ext_count;		/* # of hot file extension */
	__le16  s_encoding;		/* Filename charset encoding */
	__le16  s_encoding_flags;	/* Filename charset encoding flags */
	__u8 s_stop_reason[MAX_STOP_REASON];	/* stop checkpoint reason */
	__u8 s_errors[MAX_F2FS_ERRORS];		/* reason of image corrupts */
	__u8 reserved[258];		/* valid reserved region */
	__le32 crc;			/* checksum of superblock */
} __packed;

SuperBlock的内容在格式化时候就被确定，通常不会被修改，为了更好的适配VFS层，放在磁盘第一个扇区。它的主要作用是记录整个文件系统的分区信息，包括总的block的数量、已使用的block数量、各区的起始地址、F2FS的默认参数、支持的特性等。在F2FS挂载时，内存会创建一个f2fs_sb_info结构从superblock中读取相关数据。

为了避免文件系统崩溃，它具有2个备份，如果#0损坏，则使用#1恢复，

(2) CheckPoint

该区域占2个segment（4MB），记录了上次卸载F2FS时刻，系统的block、node的分配状态，用于下次挂载F2FS时，恢复整个系统的block，node分配状态，主要作用就是为了保持数据一致性

struct f2fs_checkpoint {
	__le64 checkpoint_ver;		/* checkpoint block version number */
	__le64 user_block_count;	/* # of user blocks */
	__le64 valid_block_count;	/* # of valid blocks in main area */
	__le32 rsvd_segment_count;	/* # of reserved segments for gc */
	__le32 overprov_segment_count;	/* # of overprovision segments */
	__le32 free_segment_count;	/* # of free segments in main area */

	/* information of current node segments */
	__le32 cur_node_segno[MAX_ACTIVE_NODE_LOGS];
	__le16 cur_node_blkoff[MAX_ACTIVE_NODE_LOGS];
	/* information of current data segments */
	__le32 cur_data_segno[MAX_ACTIVE_DATA_LOGS];
	__le16 cur_data_blkoff[MAX_ACTIVE_DATA_LOGS];
	__le32 ckpt_flags;		/* Flags : umount and journal_present */
	__le32 cp_pack_total_block_count;	/* total # of one cp pack */
	__le32 cp_pack_start_sum;	/* start block number of data summary */
	__le32 valid_node_count;	/* Total number of valid nodes */
	__le32 valid_inode_count;	/* Total number of valid inodes */
	__le32 next_free_nid;		/* Next free node number */
	__le32 sit_ver_bitmap_bytesize;	/* Default value 64 */
	__le32 nat_ver_bitmap_bytesize; /* Default value 256 */
	__le32 checksum_offset;		/* checksum offset inside cp block */
	__le64 elapsed_time;		/* mounted time */
	/* allocation type of current segment */
	unsigned char alloc_type[MAX_ACTIVE_LOGS];

	/* SIT and NAT version bitmap */
	unsigned char sit_nat_version_bitmap[];
} __packed;

在运行中，F2FS会定期将当前分配状态写入CheckPoint区域，采用“乒乓操作”，如上次写入的是cp#0，下次就会写入cp#1，在此数据结构中有一个checkpoint_ver用来记录版本，如果两个cp都能用，则会选择最新的那个

CheckPoint一般只在F2FS启动时候被读取，用于数据恢复，在运行过程中大部分都是被写，用于记录恢复信息。当F2FS需要通过fsync或umount等命令对系统同步时，F2FS会触发一次CheckPoint机制，主要完成以下工作

a.页缓存的脏node和dentry block会刷写回到磁盘;
b.挂起系统其他的写行为，如create，unlink，mkdir；
c.将系统的meta data，如NAT、SIT、SSA的数据写回磁盘;
d.更新checkpoint的状态，包括checkpoint的版本，NAT和SIT的bitmaps以及journals，SSA，Orphan inode

(3) SIT

SIT（Segment Information Table）区域记录了Main area中各个segment的详细信息，例如该segment中Valid 以及修改时间等，配合GC流程的选择策略，它的大小由Main Area所占用的segment数量确定的

struct f2fs_sm_info {
	struct sit_info *sit_info;		/* whole segment information */
	struct free_segmap_info *free_info;	/* free segment information */
	struct dirty_seglist_info *dirty_info;	/* dirty segment information */
	struct curseg_info *curseg_array;	/* active segment information */

	struct f2fs_rwsem curseg_lock;	/* for preventing curseg change */

	block_t seg0_blkaddr;		/* block address of 0'th segment */
	block_t main_blkaddr;		/* start block address of main area */
	block_t ssa_blkaddr;		/* start block address of SSA area */

	unsigned int segment_count;	/* total # of segments */
	unsigned int main_segments;	/* # of segments in main area */
	unsigned int reserved_segments;	/* # of reserved segments */
	unsigned int additional_reserved_segments;/* reserved segs for IO align feature */
	unsigned int ovp_segments;	/* # of overprovision segments */

	/* a threshold to reclaim prefree segments */
	unsigned int rec_prefree_segments;

	struct list_head sit_entry_set;	/* sit entry set list */

	unsigned int ipu_policy;	/* in-place-update policy */
	unsigned int min_ipu_util;	/* in-place-update threshold */
	unsigned int min_fsync_blocks;	/* threshold for fsync */
	unsigned int min_seq_blocks;	/* threshold for sequential blocks */
	unsigned int min_hot_blocks;	/* threshold for hot block allocation */
	unsigned int min_ssr_sections;	/* threshold to trigger SSR allocation */

	/* for flush command control */
	struct flush_cmd_control *fcc_info;

	/* for discard command control */
	struct discard_cmd_control *dcc_info;
};

(4) NAT

NAT（Segment Information Table）区域记录了node id 与真实地址的关系，其本质是一个中间层，通过该区域，可以避免索引地址，而是索引id号（每个node都有一个nid），NAT的主要作用就是将nid翻译成Main Area中的地址信息，之前的wandering tree问题也是利用了这个区域解决的

在传统的 LFS中，由于使用直接地址索引，当某个数据块被修改后，导致该数据块的管理块递归修改。例如，在A1 -> B1 -> C1 ->D1的索引树中

a.当D1被修改后，会写入新地址D2
b.而C1索引的是D1的地址，此时该地址是invalid的，所以需要更新C1中存储的值,写入C2
c.以此类推，直到A1被写入A2快中，这就是滚雪球效应，修改一个数据引起连锁反应

A1、B1、C1---管理快
D1---数据块

引起此问题的根因是采用直接地址作为索引，F2FS解决该问题的思路是引入一个中间层，即NAT表，负责做地址翻译，避免直接索引地址

a.A1中存储B1的id号，B1存储C1的id号
b.C1直接索引D1的地址
c.当D1被修改后，只需要修改C1和NAT表中C1的地址索引即可（NAT表是inplace更新，先擦后写）
d.由于C1的id号保持不变，所以A1和B1都不需要修改

struct f2fs_nm_info {
	block_t nat_blkaddr;		/* base disk address of NAT */
	nid_t max_nid;			/* maximum possible node ids */
	nid_t available_nids;		/* # of available node ids */
	nid_t next_scan_nid;		/* the next nid to be scanned */
	nid_t max_rf_node_blocks;	/* max # of nodes for recovery */
	unsigned int ram_thresh;	/* control the memory footprint */
	unsigned int ra_nid_pages;	/* # of nid pages to be readaheaded */
	unsigned int dirty_nats_ratio;	/* control dirty nats ratio threshold */

	/* NAT cache management */
	struct radix_tree_root nat_root;/* root of the nat entry cache */
	struct radix_tree_root nat_set_root;/* root of the nat set cache */
	struct f2fs_rwsem nat_tree_lock;	/* protect nat entry tree */
	struct list_head nat_entries;	/* cached nat entry list (clean) */
	spinlock_t nat_list_lock;	/* protect clean nat entry list */
	unsigned int nat_cnt[MAX_NAT_STATE]; /* the # of cached nat entries */
	unsigned int nat_blocks;	/* # of nat blocks */

	/* free node ids management */
	struct radix_tree_root free_nid_root;/* root of the free_nid cache */
	struct list_head free_nid_list;		/* list for free nids excluding preallocated nids */
	unsigned int nid_cnt[MAX_NID_STATE];	/* the number of free node id */
	spinlock_t nid_list_lock;	/* protect nid lists ops */
	struct mutex build_lock;	/* lock for build free nids */
	unsigned char **free_nid_bitmap;
	unsigned char *nat_block_bitmap;
	unsigned short *free_nid_count;	/* free nid count of NAT block */

	/* for checkpoint */
	char *nat_bitmap;		/* NAT bitmap pointer */

	unsigned int nat_bits_blocks;	/* # of nat bits blocks */
	unsigned char *nat_bits;	/* NAT bits blocks */
	unsigned char *full_nat_bits;	/* full NAT pages */
	unsigned char *empty_nat_bits;	/* empty NAT pages */
#ifdef CONFIG_F2FS_CHECK_FS
	char *nat_bitmap_mir;		/* NAT bitmap mirror */
#endif
	int bitmap_size;		/* bitmap size */
};

(5) SSA

SSA（Segment Summary Area）区域主要保存了journal（SIT/NAT临时的修改信息）以及summary（记录逻辑地址和物理地址关系的结构），这个区域主要用于反向索引，记录了block所属的node信息

/* 4KB-sized summary block structure */
struct f2fs_summary_block {
	struct f2fs_summary entries[ENTRIES_IN_SUM];
	struct f2fs_journal journal;
	struct summary_footer footer;
} __packed;