Re: [PATCH] f2fs: optimize gc for better performance

[Jaegeuk Kim]

Hi,

2013-08-29 (ë), 08:48 +0800, Jin Xu:
> From: Jin Xu <jinuxstyle@xxxxxxxxx>
> 
> This patch improves the foreground gc efficiency by optimizing the
> victim selection policy. With this optimization, the random re-write
> performance could increase up to 20%.
> 
> For f2fs, foreground gc happens when disk is lack of free spaces,
> it selects dirty segments and moves valid blocks around for making
> more space available. The gc cost of a segment is determined by the
> valid blocks in the segment. The less the valid blocks, the higher
> the efficiency. The ideal victim segment is the one that has the
> most garbage blocks.
> 
> Currently, it searches up to 20 dirty segments for a victim segment.
> The selected victim is not likely the best victim for gc when there
> are much more dirty segments. Why not searching more dirty segments
> for a better victim? The cost of searching dirty segments is
> negligible in comparison to moving blocks.
> 
> In this patch, it does not search a constant number of dirty segments
> anymore, instead it calculates the number based on the total segments,
> dirty segments and a threshold. Following is the pseudo formula.
> 		,-- nr_dirty_segments, if total_segments < threshold
> (# of search) = |
> 		`-- (nr_dirty_segments * threshold) / total_segments,
>                         Otherwise

Nice catch, but,
I don't understand why we search the # of segments in proportion to the
# of dirty segments.
How about the case where threshold = 10 and total_segments = 100000?
Or threshold = 1000000 and total_segments = 100?
For this, we need to define additional MIN/MAX thresholds and another
handling codes as your proposal.

> 
> The test case is simple. It creates as many files until the disk full.
> The size for each file is 32KB. Then it writes as many as 100000
> records of 4KB size to random offsets of random files in sync mode.
> The testing was done on a 2GB partition of a SDHC card. Let's see the
> test result of f2fs without and with the patch.

It seems that we can obtain the performance gain just by setting the
MAX_VICTIM_SEARCH to 4096, for example.
So, how about just adding an ending criteria like below?

[snip]

> diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
> index 35f9b1a..4e045e6 100644
> --- a/fs/f2fs/gc.c
> +++ b/fs/f2fs/gc.c
> @@ -138,10 +138,12 @@ static void select_policy(struct f2fs_sb_info *sbi, int gc_type,
>  	if (p->alloc_mode == SSR) {
>  		p->gc_mode = GC_GREEDY;
>  		p->dirty_segmap = dirty_i->dirty_segmap[type];
> +		p->dirty_type = type;

		p->max_search = dirty_i->nr_dirty[type];

>  		p->ofs_unit = 1;
>  	} else {
>  		p->gc_mode = select_gc_type(gc_type);
>  		p->dirty_segmap = dirty_i->dirty_segmap[DIRTY];
> +		p->dirty_type = DIRTY;

		p->max_search = dirty_i->nr_dirty[DIRTY];

>  		p->ofs_unit = sbi->segs_per_sec;
>  	}

	if (p->max_search > MAX_VICTIM_SEARCH)
		p->max_search = MAX_VICTIM_SEARCH;

#define MAX_VICTIM_SEARCH 4096 /* covers 8GB */

>  	p->offset = sbi->last_victim[p->gc_mode];
> @@ -243,6 +245,8 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
>  	struct victim_sel_policy p;
>  	unsigned int secno, max_cost;
>  	int nsearched = 0;
> +	unsigned int max_search = MAX_VICTIM_SEARCH;
> +	unsigned int nr_dirty;
>  
>  	p.alloc_mode = alloc_mode;
>  	select_policy(sbi, gc_type, type, &p);
> @@ -258,6 +262,27 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
>  			goto got_it;
>  	}
>  
> +	nr_dirty = dirty_i->nr_dirty[p.dirty_type];
> +	if (p.gc_mode == GC_GREEDY && p.alloc_mode != SSR) {
> +		if (TOTAL_SEGS(sbi) <= FULL_VICTIM_SEARCH_THRESH)
> +			max_search = nr_dirty; /* search all the dirty segs */
> +		else {
> +			/*
> +			 * With more dirty segments, garbage blocks are likely
> +			 * more scattered, thus search harder for better
> +			 * victim.
> +			 */
> +			max_search = div_u64 ((nr_dirty *
> +				FULL_VICTIM_SEARCH_THRESH), TOTAL_SEGS(sbi));
> +			if (max_search < MIN_VICTIM_SEARCH_GREEDY)
> +				max_search = MIN_VICTIM_SEARCH_GREEDY;
> +		}
> +	}
> +
> +	/* no more than the total dirty segments */
> +	if (max_search > nr_dirty)
> +		max_search = nr_dirty;
> +
>  	while (1) {
>  		unsigned long cost;
>  		unsigned int segno;
> @@ -290,7 +315,7 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
>  		if (cost == max_cost)
>  			continue;
>  
> -		if (nsearched++ >= MAX_VICTIM_SEARCH) {
> +		if (nsearched++ >= max_search) {

		if (nsearched++ >= p.max_search) {

>  			sbi->last_victim[p.gc_mode] = segno;
>  			break;
>  		}
> diff --git a/fs/f2fs/gc.h b/fs/f2fs/gc.h
> index 2c6a6bd..2f525aa 100644
> --- a/fs/f2fs/gc.h
> +++ b/fs/f2fs/gc.h
> @@ -20,7 +20,9 @@
>  #define LIMIT_FREE_BLOCK	40 /* percentage over invalid + free space */
>  
>  /* Search max. number of dirty segments to select a victim segment */
> -#define MAX_VICTIM_SEARCH	20
> +#define MAX_VICTIM_SEARCH		20
> +#define MIN_VICTIM_SEARCH_GREEDY	20
> +#define FULL_VICTIM_SEARCH_THRESH	4096
>  
>  struct f2fs_gc_kthread {
>  	struct task_struct *f2fs_gc_task;
> diff --git a/fs/f2fs/segment.h b/fs/f2fs/segment.h
> index 062424a..cd33f96 100644
> --- a/fs/f2fs/segment.h
> +++ b/fs/f2fs/segment.h
> @@ -142,6 +142,7 @@ struct victim_sel_policy {
>  	int alloc_mode;			/* LFS or SSR */
>  	int gc_mode;			/* GC_CB or GC_GREEDY */
>  	unsigned long *dirty_segmap;	/* dirty segment bitmap */
> +	int dirty_type;

	int max_search;		/* maximum # of segments to search */

>  	unsigned int offset;		/* last scanned bitmap offset */
>  	unsigned int ofs_unit;		/* bitmap search unit */
>  	unsigned int min_cost;		/* minimum cost */

-- 
Jaegeuk Kim
Samsung

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/