F2FS GC victim segment 选择策略

由于Log-Structured结构，F2FS文件系统的可用空间会快速被消耗，因此需要引入垃圾回收(GC)来回收空间。

本源码阅读主要为个人阅读F2FS GC源码过程中的记录，主要介绍以下内容。

1. 介绍f2fs gc的主体流程
2. 【当前】介绍victim segment选择策略（涉及一定的SSR机制相关的内容）
3. 介绍GC的执行过程

在每部分内容中，会对涉及的关键数据结构进行阅读与记录，并分析函数的执行流程与若干细节。

f2fs_get_victim函数(选择victim segment的核心函数)

在空间不足时，F2FS会进行GC操作来腾出空闲空间。

segment(默认情况下为2MB，包含512个block)是F2FS GC的基本单位。在实际进行有效块的识别和迁移之前，首先需要使用victim segment选择策略找到GC收益/性价比最高的segment，从而进行数据迁移与segment的回收。

函数f2fs_get_victim是实现上述victim segment selection的关键函数。后来，由于SSR机制的引入、以及SSR机制在segment的选取逻辑上与F2FS GC选取逻辑上有着相近之处，因此该函数还同时被用于SSR目标segment的选取。

1. 涉及的关键结构体

1.1 结构体victim_sel_policy：设定GC策略 (fs/f2fs/segment.h)

/* for a function parameter to select a victim segment */
struct victim_sel_policy {
	int alloc_mode;			/* LFS or SSR */
	int gc_mode;			/* GC_CB or GC_GREEDY */
	unsigned long *dirty_bitmap;	/* dirty segment/section bitmap */
	unsigned int max_search;	/*
					 * maximum # of segments/sections
					 * to search
					 */
	unsigned int offset;		/* last scanned bitmap offset */
	unsigned int ofs_unit;		/* bitmap search unit */
	unsigned int min_cost;		/* minimum cost */
	unsigned long long oldest_age;	/* oldest age of segments having the same min cost */
	unsigned int min_segno;		/* segment # having min. cost */
	unsigned long long age;		/* mtime of GCed section*/
	unsigned long long age_threshold;/* age threshold */
};

• alloc_mode：分配器策略，支持LFS或者SSR（还有AT_SSR，若有需要再补充）。

  LFS是GC选择待待回收segment场景，而SSR是SSR分配策略选择segment的场景。

• gc_mode：本次GC的策略，常见有GC_CB和GC_GREEDY两种

• dirty_bitmap：对应segment管理的dirty_segmap字段，一共有8中类型的脏数据，

  • DIRTY_HOT/WARM/COLD_DATA和DIRTY_HOT/WARM/COLD_NODE类型用于SSR分配场景；

  • DIRTY:更多用于GC场景
  • PRE表示没有可用block的segment，等待CP流程将其释放。

• max_search、offset：最多搜索次数和上次搜索后的偏移值，用于搜索dirty_bitmap中的内容。

• min_cost：最小开销，用于上述两种GC策略的比较。

• min_segno：根据GC策略选择的最小segment号。

• ofs_unit：bitmap search unit，遍历单位。LFS模式下用sbi->segs_per_sec赋值(默认为1)，SSR模式下直接赋1

1.2 结构体：f2fs_sb_info：最常用的super block信息结构体(fs/f2fs/f2fs.h)

struct f2fs_sb_info {//(暂时仅列出用于GC的成员)
    
    struct dirty_seglist_info *dirty_info;	/* dirty segment information，*/
    // GC时,根据情况给结构体victim_sel_policy的dirty_bitmap赋值
    										
    ...
   	/* for cleaning operations */
	struct f2fs_rwsem gc_lock;		/*
						 * semaphore for GC, avoid
						 * race between GC and GC or CP
						 */
	struct f2fs_gc_kthread	*gc_thread;	/* GC thread */
	struct atgc_management am;		/* atgc management */
	unsigned int cur_victim_sec;		/* current victim section num */
	unsigned int gc_mode;			/* current GC state */
	unsigned int next_victim_seg[2];	/* next segment in victim section */
	spinlock_t gc_remaining_trials_lock;
	/* remaining trial count for GC_URGENT_* and GC_IDLE_* */
	unsigned int gc_remaining_trials;
    ...
}

2. f2fs_get_victim函数

f2fs_get_victim函数有两种调用方式：GC 和 SSR segment selection

• GC：选择victim segment，且不从victim seglist中移除
• SSR：选择含有最少valid blocks数量的segment，并从victim seglist中移除

下面介绍该函数的执行过程，若只想关注总体流程，可直接跳转至总结。

1. 设定结构体victim_sel_policy p

2. 设定p的初始值

   调用函数select_policy(传入sbi、gc_type、type、victim_sel_policy结构体&p)

   函数作用：设置p的gc_mode(GC策略)、max_search(最多搜索次数)、dirty_bitmap、offset(victim semgent的bitmap offset)等参数

   1. 根据alloc mode进行相关设置

      • alloc_mode为SSR时，将gc_mode设置为GC_GREEDY，将搜索范围max_search设置为整个dirty seglist

      • alloc_mode为AT_SSR时，策略同SSR

      • alloc_mode为LFS时，根据gc_type得到GC mode

        此处留了一些接口，若segment和section大小发生变化时会发生些许变化。

        默认情况下，该函数的max_search也设置为整个dirty seglist

   2. 调整max_search范围

      仅在BG_GC、gc_mode非URGENT、GC_AT、AT_SSR等模式下时进行如下设置

      max_search=min(max_search, sbi->max_victim_search)

   3. 设置结构体p的offset (bitmap offset)，在dirty bitmap中遍历寻找victim segment的起始偏移量

      • mount_opt.fs_mode为FS_MODE_FRAGMENT_SEG或FS_MODE_FRAGMENT_BLK时

        bitmap offset设置为随机数

      • mount_opt.opt为NOHEAP模式时，且类型为directory entry blocks或node blocks时

        bitmap offset设置为0

      • 否则将bitmap设置为同样gc_mode的上一次处理到的victim segment的偏移位置

      	if (f2fs_need_rand_seg(sbi))//判断条件；m
      		p->offset = prandom_u32_max(MAIN_SECS(sbi) * sbi->segs_per_sec);
      		//随机指定到当前section中的某个偏移量
      	else if (test_opt(sbi, NOHEAP) &&
      		(type == CURSEG_HOT_DATA || IS_NODESEG(type)))
      		p->offset = 0;
      	else
      		p->offset = SIT_I(sbi)->last_victim[p->gc_mode];
      

3. 选取victim segment(p.min_segno存储当前策略下选取的victim segno)

   

   • result(目标回收的segno)已经指定的情况下，判断当前result是否可用（一般仅在ioctl场景会使用）

     (需要包含有效块,且不为当前正在处理的curseg队列中，且不是当前已选择的victim segment)

   • result未指定

     1. p.max_search为0，达到搜索边界，退出

     2. 若当前为FG_GC，且alloc_mode为LFS(非SSR模式)则能够使用上次BG_GC选取的segment

        原因可能是因为需要加快速度，快速得到使用空间，直接使用上次未完成的BGGC的选取结果，存储到p.min_segno中，并跳转至got_it。

     3. 若上述步骤都无法找到合适的victim segment，则真正开始通过dirty bitmap遍历查找，通过find_next_bit找到dirty bitmap中合适的segno

        该遍历方式为循环单向遍历，从当前p.offset开始，若遍历至bitmap尾，则从头开始继续遍历，直到遍历一圈。

     4. 根据alloc_mode进行条件判断

        • LFS模式下：若该segment含有上次cp过的有效块，则跳过目前segment，继续循环遍历

          （Dont touch checkpointed data）

        • SSR模式下：若当前segment已经没有空闲块，则跳过目前segment，继续循环遍历

          判断条件: !f2fs_segment_has_free_slot(sbi, segno)

     5. 根据gc_type进行条件判断

        • BGGC：若当前segment已在BGC victims中，则跳过
        • FGGC：若为pinned segment，则跳过
        • ATGC：暂略

     6. 若通过了4、5的条件判断，则表明当前segno有效

        计算当前segno在当前gc策略下的cost(get_gc_cost)，更新p.min_segno、p.min_cost等信息

     7. 若已经达到搜索边界，则更新p->last_victim[p.gc_mode]信息，并退出循环

4. got_it (got_result)：找到了victim segno，将结果存到result中，并修改sbi->cur_victim_sec、dirty_seglist_info中对应的信息

   

总结：f2fs_get_victim函数的总体流程如下：

1. 若当前是FG_GC时，则尽量不进入循环搜索，直接使用BG_GC的选取结果(为了加快选取速度)

2. 开始进入循环搜索。

   1. 首先根据find_next_bit函数，从p.dirty_segmap中找到第一个dirty的segment出来(搜索方式为单向循环搜索)。
   2. 然后，对该segment进行若干条件判断
      • GC模式下，要求其不能包含上一次刚CP过的有效块
      • SSR模式下，要求其不能不含空闲块
   3. 经过条件判断后，通过get_gc_cost函数计算segment的cost，并判断是否小于p.min_cost，然后进行赋值

   循环在达到了最大的搜索次数之后退出，*result存储了选取的segno。

3. get_gc_cost函数

F2FS中，通过变量cost来表示开销。在进行层层segment可用性筛选后，再对这些经过筛选的segment进行cost的计算，从而选择最佳的segment。由于SSR机制与F2FS GC由于逻辑相近，因此共用f2fs_get_victim接口，只需在计算cost阶段修改相应的逻辑即可。

• F2FS GC模式：常见的victim segment选择策略如下：

  • 前台GC：采用greedy policy，选取有效块最少的section

  • 后台GC：采用cost-benefit策略，根据利用率以及”age“来选择victim section

    算法：cost_benefit = (1-u)/2u*age,结果越大，越值得cleaning
        
    u表示valid block 在该section中的比例
    1-u表示无效块的比例，即GC收益。
    2u表示对这个section进行GC的开销（读取Valid block（1个u）并写到新的segment中（1个u）
    age表示上一次修改距离现在的时间差
    

• SSR模式：segment有效块最多，cost越大，越不会选取该segment

  因为SSR模式下，系统希望选取的segment中包含的无效块/空闲块越多越好(即有效块越少越好)，这样就有更多的空间提供新数据的覆盖写入。

static inline unsigned int get_gc_cost(struct f2fs_sb_info *sbi,
			unsigned int segno, struct victim_sel_policy *p)
{
	if (p->alloc_mode == SSR)
		return get_seg_entry(sbi, segno)->ckpt_valid_blocks;

	/* alloc_mode == LFS */
	if (p->gc_mode == GC_GREEDY)
		return get_valid_blocks(sbi, segno, sbi->segs_per_sec); // Greedy算法，valid block越多表示cost越大，越不值得gc
	else
		return get_cb_cost(sbi, segno); // Cost-Benefit算法，这个是考虑了访问时间和valid block开销的算法
}

源码 f2fs_get_victim

/*
 * This function is called from two paths.
 * One is garbage collection and the other is SSR segment selection.
 * When it is called during GC, it just gets a victim segment
 * and it does not remove it from dirty seglist.
 * When it is called from SSR segment selection, it finds a segment
 * which has minimum valid blocks and removes it from dirty seglist.
 */
int f2fs_get_victim(struct f2fs_sb_info *sbi, unsigned int *result,
			int gc_type, int type, char alloc_mode,
			unsigned long long age)
{
	struct dirty_seglist_info *dirty_i = DIRTY_I(sbi);
	struct sit_info *sm = SIT_I(sbi);
	struct victim_sel_policy p;
	unsigned int secno, last_victim;
	unsigned int last_segment;
	unsigned int nsearched;
	bool is_atgc;
	int ret = 0;

	mutex_lock(&dirty_i->seglist_lock);
	last_segment = MAIN_SECS(sbi) * sbi->segs_per_sec;

	p.alloc_mode = alloc_mode;
	p.age = age;
	p.age_threshold = sbi->am.age_threshold;

retry:
	select_policy(sbi, gc_type, type, &p);
	p.min_segno = NULL_SEGNO;
	p.oldest_age = 0;
	p.min_cost = get_max_cost(sbi, &p);

	is_atgc = (p.gc_mode == GC_AT || p.alloc_mode == AT_SSR);
	nsearched = 0;

	if (is_atgc)
		SIT_I(sbi)->dirty_min_mtime = ULLONG_MAX;

	if (*result != NULL_SEGNO) {
		if (!get_valid_blocks(sbi, *result, false)) {
			ret = -ENODATA;
			goto out;
		}

		if (sec_usage_check(sbi, GET_SEC_FROM_SEG(sbi, *result)))
			ret = -EBUSY;
		else
			p.min_segno = *result;
		goto out;
	}

	ret = -ENODATA;
	if (p.max_search == 0)
		goto out;

	if (__is_large_section(sbi) && p.alloc_mode == LFS) {
		if (sbi->next_victim_seg[BG_GC] != NULL_SEGNO) {
			p.min_segno = sbi->next_victim_seg[BG_GC];
			*result = p.min_segno;
			sbi->next_victim_seg[BG_GC] = NULL_SEGNO;
			goto got_result;
		}
		if (gc_type == FG_GC &&
				sbi->next_victim_seg[FG_GC] != NULL_SEGNO) {
			p.min_segno = sbi->next_victim_seg[FG_GC];
			*result = p.min_segno;
			sbi->next_victim_seg[FG_GC] = NULL_SEGNO;
			goto got_result;
		}
	}

	last_victim = sm->last_victim[p.gc_mode];
	if (p.alloc_mode == LFS && gc_type == FG_GC) {
		p.min_segno = check_bg_victims(sbi);
		if (p.min_segno != NULL_SEGNO)
			goto got_it;
	}

	while (1) {
		unsigned long cost, *dirty_bitmap;
		unsigned int unit_no, segno;

		dirty_bitmap = p.dirty_bitmap;
		unit_no = find_next_bit(dirty_bitmap,
				last_segment / p.ofs_unit,
				p.offset / p.ofs_unit);
		segno = unit_no * p.ofs_unit;
		if (segno >= last_segment) {
			if (sm->last_victim[p.gc_mode]) {
				last_segment =
					sm->last_victim[p.gc_mode];
				sm->last_victim[p.gc_mode] = 0;
				p.offset = 0;
				continue;
			}
			break;
		}

		p.offset = segno + p.ofs_unit;
		nsearched++;

#ifdef CONFIG_F2FS_CHECK_FS
		/*
		 * skip selecting the invalid segno (that is failed due to block
		 * validity check failure during GC) to avoid endless GC loop in
		 * such cases.
		 */
		if (test_bit(segno, sm->invalid_segmap))
			goto next;
#endif

		secno = GET_SEC_FROM_SEG(sbi, segno);

		if (sec_usage_check(sbi, secno))
			goto next;

		/* Don't touch checkpointed data */
		if (unlikely(is_sbi_flag_set(sbi, SBI_CP_DISABLED))) {
			if (p.alloc_mode == LFS) {
				/*
				 * LFS is set to find source section during GC.
				 * The victim should have no checkpointed data.
				 */
				if (get_ckpt_valid_blocks(sbi, segno, true))
					goto next;
			} else {
				/*
				 * SSR | AT_SSR are set to find target segment
				 * for writes which can be full by checkpointed
				 * and newly written blocks.
				 */
				if (!f2fs_segment_has_free_slot(sbi, segno))
					goto next;
			}
		}

		if (gc_type == BG_GC && test_bit(secno, dirty_i->victim_secmap))
			goto next;

		if (gc_type == FG_GC && f2fs_section_is_pinned(dirty_i, secno))
			goto next;

		if (is_atgc) {
			add_victim_entry(sbi, &p, segno);
			goto next;
		}

		cost = get_gc_cost(sbi, segno, &p);

		if (p.min_cost > cost) {
			p.min_segno = segno;
			p.min_cost = cost;
		}
next:
		if (nsearched >= p.max_search) {
			if (!sm->last_victim[p.gc_mode] && segno <= last_victim)
				sm->last_victim[p.gc_mode] =
					last_victim + p.ofs_unit;
			else
				sm->last_victim[p.gc_mode] = segno + p.ofs_unit;
			sm->last_victim[p.gc_mode] %=
				(MAIN_SECS(sbi) * sbi->segs_per_sec);
			break;
		}
	}

	/* get victim for GC_AT/AT_SSR */
	if (is_atgc) {
		lookup_victim_by_age(sbi, &p);
		release_victim_entry(sbi);
	}

	if (is_atgc && p.min_segno == NULL_SEGNO &&
			sm->elapsed_time < p.age_threshold) {
		p.age_threshold = 0;
		goto retry;
	}

	if (p.min_segno != NULL_SEGNO) {
got_it:
		*result = (p.min_segno / p.ofs_unit) * p.ofs_unit;
got_result:
		if (p.alloc_mode == LFS) {
			secno = GET_SEC_FROM_SEG(sbi, p.min_segno);
			if (gc_type == FG_GC)
				sbi->cur_victim_sec = secno;
			else
				set_bit(secno, dirty_i->victim_secmap);
		}
		ret = 0;

	}
out:
	if (p.min_segno != NULL_SEGNO)
		trace_f2fs_get_victim(sbi->sb, type, gc_type, &p,
				sbi->cur_victim_sec,
				prefree_segments(sbi), free_segments(sbi));
	mutex_unlock(&dirty_i->seglist_lock);

	return ret;
}