Linux-f2fs-devel Archive on
 help / color / Atom feed
From: Chao Yu <>
To: <>
Subject: [f2fs-dev] [PATCH 0/5] Support Age-Threshold based Garbage Collection for f2fs
Date: Tue, 7 Jul 2020 19:21:23 +0800
Message-ID: <> (raw)

This patch series introduce a new garbage collection algorithm named ATGC
(Age Threshold based Garbage Collection) in order to enhance efficiency and
effect of background garbage collection.

ATGC algorithm tries to fliter few oldest candidates according to defined
age threshold, it selects source section in those candidates and then
select target segment which has almost the same age of source section,
finally, it migrates valid blocks from source section into target segment
with SSR allocator, enhancement shows in below aspects:
- it avoids selecting young victim section which may have high update
- SSR write avoids unneeded movement of blocks locate in target segment;
- source section and target segment has almost the same age (update
frequency), it keeps well hot/cold separation effect;

Patch 1 introduces in-memory curseg, since it only exists in memory, so it
avoids on-disk layout change whenever we want to add a new type of log.
Firstly, adapting aligned pinfile allocation to use in-memory curseg,
later, we will use in-memory curseg in ATGC feature for migration as well.

Patch 2 changes segment's mtime definition from recording last update time
to recording average update time, so that it can indicate more precise
update time of each valid blocks in segment.

Patch 3 changes segment mtime update policy during GC, 1) don't update
original segment's mtime; 2) inherit segment's mtime from original segment
to target segment.

Patch 4 adds to support 64-bits key in rb-tree node entry, and introduce
f2fs_lookup_rb_tree_ext() to support lookup functionality with 64-bits key.

Patch 5 adds to support ATGC skeleton to enhance effect and efficiency
of BGGC.

Test and result:
- create 160 dirty segments:
 * half of them have 128 valid blocks per segment
 * left of them have 384 valid blocks per segment
- run background GC

Benefit: GC count and block movement count both decrease obviously:

- Before:
GC calls: 162 (BG: 220)

Try to move 41454 blocks (BG: 41454)
  - data blocks : 40960 (40960)

SSR: 0 blocks in 0 segments
LFS: 41364 blocks in 81 segments

- After:
GC calls: 75 (BG: 76)

Try to move 12813 blocks (BG: 12813)
  - data blocks : 12544 (12544)
SSR: 12032 blocks in 77 segments
LFS: 855 blocks in 2 segments

Chao Yu (5):
  f2fs: introduce inmem curseg
  f2fs: record average update time of segment
  f2fs: inherit mtime of original block during GC
  f2fs: support 64-bits key in f2fs rb-tree node entry
  f2fs: support age threshold based garbage collection

 fs/f2fs/checkpoint.c        |   7 +-
 fs/f2fs/data.c              |   2 +-
 fs/f2fs/debug.c             |  10 +-
 fs/f2fs/extent_cache.c      |  37 +++-
 fs/f2fs/f2fs.h              |  50 ++++-
 fs/f2fs/file.c              |   3 +-
 fs/f2fs/gc.c                | 373 +++++++++++++++++++++++++++++++++++-
 fs/f2fs/gc.h                |  25 +++
 fs/f2fs/segment.c           | 331 +++++++++++++++++++++++++-------
 fs/f2fs/segment.h           |  40 +++-
 fs/f2fs/super.c             |  19 +-
 include/trace/events/f2fs.h |   8 +-
 12 files changed, 798 insertions(+), 107 deletions(-)


Linux-f2fs-devel mailing list

             reply index

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-07-07 11:21 Chao Yu [this message]
2020-07-07 11:21 ` [f2fs-dev] [PATCH 1/5] f2fs: introduce inmem curseg Chao Yu
2020-07-26 16:03   ` Jaegeuk Kim
2020-07-27  1:26     ` Chao Yu
2020-07-07 11:21 ` [f2fs-dev] [PATCH 2/5] f2fs: record average update time of segment Chao Yu
2020-07-07 11:21 ` [f2fs-dev] [PATCH 3/5] f2fs: inherit mtime of original block during GC Chao Yu
2020-07-26 16:05   ` Jaegeuk Kim
2020-07-27  1:29     ` Chao Yu
2020-07-07 11:21 ` [f2fs-dev] [PATCH 4/5] f2fs: support 64-bits key in f2fs rb-tree node entry Chao Yu
2020-07-07 11:21 ` [f2fs-dev] [PATCH 5/5] f2fs: support age threshold based garbage collection Chao Yu

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-f2fs-devel Archive on

Archives are clonable:
	git clone --mirror linux-f2fs-devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-f2fs-devel linux-f2fs-devel/ \
	public-inbox-index linux-f2fs-devel

Example config snippet for mirrors

Newsgroup available over NNTP:

AGPL code for this site: git clone