[f2fs] Support ssr block allocation
It implements the ssr block allocation, and
it is triggered when # of freesections < # of OP sections.
For testing, it introduces a new gn variable 'f2fs_force_ssr'
that enforces every block allocation in a ssr manner if it is set to true.
Test: fx test fs-tests
Failed tests: RwFullDiskTest.PartialWriteSucceedsForFullDisk/F2fs
Test:
- linux host:
fx emu -N --headless -hda third_party/f2fs/test_files/blk1g.bin
- fuchsia vm:
mkdir /tmp/data;mount /dev/class/block/000 /tmp/data
cp /tmp/data/100mb.bin /tmp/data/100mb.bin.2
umount /tmp/data;dm shutdown
- linux host:
fsck.f2fs third_party/f2fs/test_files/blk1g.bin
mount third_party/f2fs/test_files/blk1g.bin ~/mnt
diff ~/mnt/100mb.bin ~/mnt/100mb.bin.2
umount ~/mnt
Prerequisite: set f2fs_force_ssr to true
Change-Id: I0dae89c935797eacba96b34fca56a7e0808d5aa2
Reviewed-on: https://fuchsia-review.googlesource.com/c/third_party/f2fs/+/536745
Reviewed-by: Brett Wilson <brettw@google.com>
diff --git a/BUILD.gn b/BUILD.gn
index d72c6b4..34ed37c 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -7,8 +7,11 @@
# moves out-of-tree.
declare_args() {
- # F2FS debug message for bringup product
+ # F2FS debug message
f2fs_bu_debug = false
+
+ # Enforce every allocation in a ssr manner [for test]
+ f2fs_force_ssr = false
}
static_library("f2fs") {
@@ -20,6 +23,7 @@
"dir_hash.cc",
"f2fs.cc",
"file.cc",
+ "gc.cc",
"mkfs.cc",
"namei.cc",
"node.cc",
@@ -89,6 +93,10 @@
defines = [ "F2FS_BU_DEBUG" ]
}
+ if (f2fs_force_ssr) {
+ defines = [ "F2FS_FORCE_SSR" ]
+ }
+
# TODO(fxbug.dev/69585): This target uses raw zx::channel with LLCPP which is deprecated.
# Please migrate to typed channel APIs (fidl::ClientEnd<T>, fidl::ServerEnd<T>).
# See linked bug for details.
diff --git a/gc.cc b/gc.cc
new file mode 100644
index 0000000..5f92168
--- /dev/null
+++ b/gc.cc
@@ -0,0 +1,126 @@
+// Copyright 2021 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "f2fs.h"
+
+namespace f2fs {
+
+uint32_t SegMgr::GetGcCost(uint32_t segno, VictimSelPolicy *p) {
+ if (p->alloc_mode == AllocMode::kSSR)
+ return SegMgr::GetSegEntry(segno)->ckpt_valid_blocks;
+
+ ZX_ASSERT(0);
+#if 0 // porting needed
+ /* alloc_mode == kLFS */
+ if (p->gc_mode == kGcGreedy)
+ return get_valid_blocks(sbi, segno, sbi->segs_per_sec);
+ else
+ return get_cb_cost(sbi, segno);
+#endif
+}
+
+void SegMgr::SelectPolicy(GcType gc_type, CursegType type, VictimSelPolicy *p) {
+ SbInfo &sbi = fs_->GetSbInfo();
+ DirtySeglistInfo *dirty_i = GetDirtyInfo(&sbi);
+
+ if (p->alloc_mode == AllocMode::kSSR) {
+ p->gc_mode = GcMode::kGcGreedy;
+ p->dirty_segmap = dirty_i->dirty_segmap[static_cast<int>(type)];
+ p->ofs_unit = 1;
+ } else {
+ ZX_ASSERT(0);
+#if 0 // porting needed
+ p->gc_mode = select_gc_type(gc_type);
+ p->dirty_segmap = dirty_i->dirty_segmap[DIRTY];
+ p->ofs_unit = sbi->segs_per_sec;
+#endif
+ }
+
+ p->offset = sbi.last_victim[static_cast<int>(p->gc_mode)];
+}
+
+uint32_t SegMgr::GetMaxCost(VictimSelPolicy *p) {
+ SbInfo &sbi = fs_->GetSbInfo();
+
+ if (p->gc_mode == GcMode::kGcGreedy)
+ return (1 << sbi.log_blocks_per_seg) * p->ofs_unit;
+ else if (p->gc_mode == GcMode::kGcCb)
+ return kUint32Max;
+ return 0;
+}
+
+bool SegMgr::GetVictimByDefault(GcType gc_type, CursegType type, AllocMode alloc_mode,
+ uint32_t *out) {
+ SbInfo &sbi = fs_->GetSbInfo();
+ DirtySeglistInfo *dirty_i = GetDirtyInfo(&sbi);
+ VictimSelPolicy p;
+
+ p.alloc_mode = alloc_mode;
+ SelectPolicy(gc_type, type, &p);
+
+ p.min_segno = kNullSegNo;
+ p.min_cost = GetMaxCost(&p);
+
+ fbl::AutoLock lock(&dirty_i->seglist_lock);
+
+#if 0 // porting needed
+ if (p.alloc_mode == AllocMode::kLFS && gc_type == GcType::kFgGC) {
+ p.min_segno = check_bg_victims(sbi);
+ if (p.min_segno != kNullSegNo)
+ goto got_it;
+ }
+#endif
+
+ uint32_t nsearched = 0;
+
+ while (1) {
+ uint32_t segno = find_next_bit_le(p.dirty_segmap, TotalSegs(&sbi), p.offset);
+ if (segno >= TotalSegs(&sbi)) {
+ if (sbi.last_victim[static_cast<int>(p.gc_mode)]) {
+ sbi.last_victim[static_cast<int>(p.gc_mode)] = 0;
+ p.offset = 0;
+ continue;
+ }
+ break;
+ }
+ p.offset = ((segno / p.ofs_unit) * p.ofs_unit) + p.ofs_unit;
+
+ if (test_bit(segno, dirty_i->victim_segmap[static_cast<int>(GcType::kFgGc)]))
+ continue;
+ if (gc_type == GcType::kBgGc &&
+ test_bit(segno, dirty_i->victim_segmap[static_cast<int>(GcType::kBgGc)]))
+ continue;
+ if (IsCurSec(&sbi, GetSecNo(&sbi, segno)))
+ continue;
+
+ uint32_t cost = GetGcCost(segno, &p);
+
+ if (p.min_cost > cost) {
+ p.min_segno = segno;
+ p.min_cost = cost;
+ }
+
+ if (cost == GetMaxCost(&p))
+ continue;
+
+ if (nsearched++ >= kMaxSearchLimit) {
+ sbi.last_victim[static_cast<int>(p.gc_mode)] = segno;
+ break;
+ }
+ }
+#if 0 // porting needed
+got_it:
+#endif
+ if (p.min_segno != kNullSegNo) {
+ *out = (p.min_segno / p.ofs_unit) * p.ofs_unit;
+ if (p.alloc_mode == AllocMode::kLFS) {
+ for (uint32_t i = 0; i < p.ofs_unit; i++)
+ set_bit(*out + i, dirty_i->victim_segmap[static_cast<int>(gc_type)]);
+ }
+ }
+
+ return (p.min_segno == kNullSegNo) ? false : true;
+}
+
+} // namespace f2fs
diff --git a/segment.cc b/segment.cc
index 9ddddb4..9b5a917 100644
--- a/segment.cc
+++ b/segment.cc
@@ -200,15 +200,18 @@
}
inline bool SegMgr::NeedSSR() {
+#ifdef F2FS_FORCE_SSR
+ return true;
+#else
+ // TODO: need to consider allocation mode and gc mode
return (FreeSections() < static_cast<uint32_t>(OverprovisionSections()));
+#endif
}
inline int SegMgr::GetSsrSegment(CursegType type) {
SbInfo &sbi = fs_->GetSbInfo();
CursegInfo *curseg = CURSEG_I(&sbi, type);
- return GetDirtyInfo(&sbi)->v_ops->get_victim(
- &sbi, &(curseg)->next_segno, static_cast<int>(GcType::kBgGc), static_cast<int>(type),
- static_cast<uint8_t>(AllocMode::kSSR));
+ return GetVictimByDefault(GcType::kBgGc, type, AllocMode::kSSR, &(curseg->next_segno));
}
inline bool SegMgr::HasNotEnoughFreeSecs() {
@@ -931,17 +934,11 @@
// ofs_unit = NeedSSR() ? 1 : sbi.segs_per_sec;
// curseg->next_segno = CheckPrefreeSegments(ofs_unit, type);
- // if (curseg->next_segno != kNullSegNo)
- // ChangeCurseg(type, false);
- // else
-
- if (type == CursegType::kCursegWarmNode) {
+ if (curseg->next_segno != kNullSegNo) {
+ ChangeCurseg(type, false);
+ } else if (type == CursegType::kCursegWarmNode) {
NewCurseg(type, false);
- } else if (false) {
-#if 0 // porting needed
- // TODO: IMPL (SSR)
- //} else if (NeedSSR() && GetSsrSegment(type)) {
-#endif
+ } else if (NeedSSR() && GetSsrSegment(type)) {
ChangeCurseg(type, true);
} else {
NewCurseg(type, false);
@@ -968,7 +965,7 @@
i <= static_cast<int>(CursegType::kCursegColdData); i++) {
curseg = CURSEG_I(&sbi, static_cast<CursegType>(i));
old_curseg = curseg->segno;
- GetSitInfo(&sbi)->s_ops->allocate_segment(&sbi, i, true);
+ AllocateSegmentByDefault(static_cast<CursegType>(i), true);
LocateDirtySegment(old_curseg);
}
}
diff --git a/segment.h b/segment.h
index 7e58259..2050130 100644
--- a/segment.h
+++ b/segment.h
@@ -8,7 +8,9 @@
namespace f2fs {
/* constant macro */
-constexpr uint32_t kNullSegNo = (uint32_t)(~0);
+constexpr uint32_t kNullSegNo = std::numeric_limits<uint32_t>::max();
+constexpr uint32_t kUint32Max = std::numeric_limits<uint32_t>::max();
+constexpr uint32_t kMaxSearchLimit = 20;
/* during checkpoint, BioPrivate is used to synchronize the last bio */
struct BioPrivate {
@@ -38,7 +40,7 @@
* GC_CB is based on cost-benefit algorithm.
* GC_GREEDY is based on greedy algorithm.
*/
-enum class GcAlgorithm { kGcCb = 0, kGcGreedy };
+enum class GcMode { kGcCb = 0, kGcGreedy };
/*
* BG_GC means the background cleaning job.
@@ -46,15 +48,15 @@
*/
enum class GcType { kBgGc = 0, kFgGc };
-/* for a function parameter to select a victim segment */
+// for a function parameter to select a victim segment
struct VictimSelPolicy {
- int alloc_mode = 0; /* LFS or SSR */
- int gc_mode = 0; /* GC_CB or GC_GREEDY */
- uint64_t *dirty_segmap = nullptr; /* dirty segment bitmap */
- uint32_t offset = 0; /* last scanned bitmap offset */
- uint32_t ofs_unit = 0; /* bitmap search unit */
- uint32_t min_cost = 0; /* minimum cost */
- uint32_t min_segno = 0; /* segment # having min. cost */
+ AllocMode alloc_mode = AllocMode::kLFS; // LFS or SSR
+ GcMode gc_mode = GcMode::kGcCb; // cost effective or greedy
+ uint64_t *dirty_segmap = nullptr; // dirty segment bitmap
+ uint32_t offset = 0; // last scanned bitmap offset
+ uint32_t ofs_unit = 0; // bitmap search unit
+ uint32_t min_cost = 0; // minimum cost
+ uint32_t min_segno = 0; // segment # having min. cost
};
struct SegEntry {
@@ -232,6 +234,37 @@
void RewriteNodePage(Page *page, Summary *sum, block_t old_blkaddr, block_t new_blkaddr);
private:
+ // GetVictimByDefault() is called for two purposes:
+ // 1) One is to select a victim segment for garbage collection, and
+ // 2) the other is to find a dirty segment used for SSR.
+ // For GC, it tries to find a victim segment that might require less cost
+ // to secure free segments among all types of dirty segments.
+ // The gc cost can be calucalted in two ways according to GcType.
+ // In case of GcType::kFgGc, it is typically triggered in the middle of user IO path,
+ // and thus it selects a victim with a less valid block count (i.e., GcMode::kGcGreedy)
+ // as it hopes the migration completes more quickly.
+ // In case of GcType::kBgGc, it is triggered at a idle time,
+ // so it uses a cost-benefit method (i.e., GcMode:: kGcCb) rather than kGcGreedy for the victim
+ // selection. kGcCb tries to find a cold segment as a victim as it hopes to mitigate a block
+ // thrashing problem.
+ // Meanwhile, SSR is to reuse invalid blocks for new block allocation, and thus
+ // it uses kGcGreedy to select a dirty segment with more invalid blocks
+ // among the same type of dirty segments as that of the current segment.
+ // |out| contains the segment number of the seleceted victim, and
+ // it returns true when it finds a victim segment.
+ bool GetVictimByDefault(GcType gc_type, CursegType type, AllocMode alloc_mode, uint32_t *out);
+
+ // This function calculates the maximum cost for a victim in each GcType
+ // Any segment with a less cost value becomes a victim candidate.
+ uint32_t GetMaxCost(VictimSelPolicy *p);
+
+ // This method determines GcMode for GetVictimByDefault
+ void SelectPolicy(GcType gc_type, CursegType type, VictimSelPolicy *p);
+
+ // This method calculates the gc cost for each dirty segment
+ uint32_t GetGcCost(uint32_t segno, VictimSelPolicy *p);
+
+ private:
F2fs *fs_;
public:
