From 093749e296e29a4b0162eb925a6701a01e8c9a98 Mon Sep 17 00:00:00 2001 From: Chao Yu Date: Tue, 4 Aug 2020 21:14:49 +0800 Subject: f2fs: support age threshold based garbage collection There are several issues in current background GC algorithm: - valid blocks is one of key factors during cost overhead calculation, so if segment has less valid block, however even its age is young or it locates hot segment, CB algorithm will still choose the segment as victim, it's not appropriate. - GCed data/node will go to existing logs, no matter in-there datas' update frequency is the same or not, it may mix hot and cold data again. - GC alloctor mainly use LFS type segment, it will cost free segment more quickly. This patch introduces a new algorithm named age threshold based garbage collection to solve above issues, there are three steps mainly: 1. select a source victim: - set an age threshold, and select candidates beased threshold: e.g. 0 means youngest, 100 means oldest, if we set age threshold to 80 then select dirty segments which has age in range of [80, 100] as candiddates; - set candidate_ratio threshold, and select candidates based the ratio, so that we can shrink candidates to those oldest segments; - select target segment with fewest valid blocks in order to migrate blocks with minimum cost; 2. select a target victim: - select candidates beased age threshold; - set candidate_radius threshold, search candidates whose age is around source victims, searching radius should less than the radius threshold. - select target segment with most valid blocks in order to avoid migrating current target segment. 3. merge valid blocks from source victim into target victim with SSR alloctor. Test steps: - 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: - Valid: 86 - Dirty: 1 - Prefree: 11 - Free: 6001 (6001) GC calls: 162 (BG: 220) - data segments : 160 (160) - node segments : 2 (2) Try to move 41454 blocks (BG: 41454) - data blocks : 40960 (40960) - node blocks : 494 (494) IPU: 0 blocks SSR: 0 blocks in 0 segments LFS: 41364 blocks in 81 segments - After: - Valid: 87 - Dirty: 0 - Prefree: 4 - Free: 6008 (6008) GC calls: 75 (BG: 76) - data segments : 74 (74) - node segments : 1 (1) Try to move 12813 blocks (BG: 12813) - data blocks : 12544 (12544) - node blocks : 269 (269) IPU: 0 blocks SSR: 12032 blocks in 77 segments LFS: 855 blocks in 2 segments Signed-off-by: Chao Yu [Jaegeuk Kim: fix a bug along with pinfile in-mem segment & clean up] Signed-off-by: Jaegeuk Kim --- include/trace/events/f2fs.h | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'include/trace') diff --git a/include/trace/events/f2fs.h b/include/trace/events/f2fs.h index 8a1c1311acac..06c73f3f6dd2 100644 --- a/include/trace/events/f2fs.h +++ b/include/trace/events/f2fs.h @@ -111,13 +111,15 @@ TRACE_DEFINE_ENUM(CP_RESIZE); #define show_alloc_mode(type) \ __print_symbolic(type, \ - { LFS, "LFS-mode" }, \ - { SSR, "SSR-mode" }) + { LFS, "LFS-mode" }, \ + { SSR, "SSR-mode" }, \ + { AT_SSR, "AT_SSR-mode" }) #define show_victim_policy(type) \ __print_symbolic(type, \ { GC_GREEDY, "Greedy" }, \ - { GC_CB, "Cost-Benefit" }) + { GC_CB, "Cost-Benefit" }, \ + { GC_AT, "Age-threshold" }) #define show_cpreason(type) \ __print_flags(type, "|", \ -- cgit v1.2.3-58-ga151 From 32c0fec1aa85f1a9aebfd9445208f4223bcd96e8 Mon Sep 17 00:00:00 2001 From: Chao Yu Date: Thu, 3 Sep 2020 10:15:15 +0800 Subject: f2fs: trace: fix typo Fixes a typo from 'compreesed' to 'compressed'. Signed-off-by: Chao Yu Signed-off-by: Jaegeuk Kim --- include/trace/events/f2fs.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/trace') diff --git a/include/trace/events/f2fs.h b/include/trace/events/f2fs.h index 06c73f3f6dd2..f8f1e85ff130 100644 --- a/include/trace/events/f2fs.h +++ b/include/trace/events/f2fs.h @@ -136,7 +136,7 @@ TRACE_DEFINE_ENUM(CP_RESIZE); __print_symbolic(type, \ { CP_NO_NEEDED, "no needed" }, \ { CP_NON_REGULAR, "non regular" }, \ - { CP_COMPRESSED, "compreesed" }, \ + { CP_COMPRESSED, "compressed" }, \ { CP_HARDLINK, "hardlink" }, \ { CP_SB_NEED_CP, "sb needs cp" }, \ { CP_WRONG_PINO, "wrong pino" }, \ -- cgit v1.2.3-58-ga151