| // 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 "src/storage/f2fs/f2fs.h" |
| |
| namespace f2fs { |
| size_t SegmentManager::GetGcCost(uint32_t segno, const VictimSelPolicy &policy) const { |
| if (policy.alloc_mode == AllocMode::kSSR) { |
| return sit_info_->sentries[segno].ckpt_valid_blocks; |
| } |
| |
| if (policy.gc_mode == GcMode::kGcGreedy) { |
| return GetValidBlocks(segno, true); |
| } |
| return GetCostBenefitRatio(segno); |
| } |
| |
| size_t SegmentManager::GetCostBenefitRatio(uint32_t segno) const { |
| size_t start = GetSecNo(segno) * superblock_info_.GetSegsPerSec(); |
| uint64_t mtime = 0; |
| for (size_t i = 0; i < superblock_info_.GetSegsPerSec(); i++) { |
| mtime += sit_info_->sentries[start + i].mtime; |
| } |
| mtime = mtime / superblock_info_.GetSegsPerSec(); |
| size_t valid_blocks_ratio = 100 * GetValidBlocks(segno, true) / superblock_info_.GetSegsPerSec() / |
| superblock_info_.GetBlocksPerSeg(); |
| |
| // Handle if the system time is changed by user |
| if (mtime < sit_info_->min_mtime) { |
| sit_info_->min_mtime = mtime ? mtime - 1 : 0; |
| } |
| if (mtime > sit_info_->max_mtime) { |
| sit_info_->max_mtime = std::max(GetMtime(), mtime + 1); |
| } |
| |
| // A higher value means that it's been longer since it was last modified. |
| size_t age = 0; |
| if (sit_info_->max_mtime != sit_info_->min_mtime) { |
| age = 100 - |
| (100 * (mtime - sit_info_->min_mtime) / (sit_info_->max_mtime - sit_info_->min_mtime)); |
| } |
| |
| return kUint32Max - (100 * (100 - valid_blocks_ratio) * age / (100 + valid_blocks_ratio)); |
| } |
| |
| VictimSelPolicy SegmentManager::GetVictimSelPolicy(GcType gc_type, CursegType type, |
| AllocMode alloc_mode) const { |
| VictimSelPolicy policy; |
| policy.alloc_mode = alloc_mode; |
| if (policy.alloc_mode == AllocMode::kSSR) { |
| policy.gc_mode = GcMode::kGcGreedy; |
| policy.dirty_segmap = &dirty_info_->dirty_segmap[static_cast<int>(type)]; |
| policy.max_search = dirty_info_->nr_dirty[static_cast<int>(type)]; |
| policy.ofs_unit = 1; |
| } else { |
| policy.gc_mode = (gc_type == GcType::kBgGc) ? GcMode::kGcCb : GcMode::kGcGreedy; |
| policy.dirty_segmap = &dirty_info_->dirty_segmap[static_cast<int>(DirtyType::kDirty)]; |
| policy.max_search = dirty_info_->nr_dirty[static_cast<int>(DirtyType::kDirty)]; |
| policy.ofs_unit = superblock_info_.GetSegsPerSec(); |
| } |
| |
| if (policy.max_search > kMaxSearchLimit) { |
| policy.max_search = kMaxSearchLimit; |
| } |
| |
| policy.offset = last_victim_[static_cast<int>(policy.gc_mode)]; |
| return policy; |
| } |
| |
| size_t SegmentManager::GetMaxCost(const VictimSelPolicy &policy) const { |
| if (policy.alloc_mode == AllocMode::kSSR) |
| return 1 << superblock_info_.GetLogBlocksPerSeg(); |
| if (policy.gc_mode == GcMode::kGcGreedy) |
| return 2 * (1 << superblock_info_.GetLogBlocksPerSeg()) * policy.ofs_unit; |
| else if (policy.gc_mode == GcMode::kGcCb) |
| return kUint32Max; |
| return 0; |
| } |
| |
| uint32_t SegmentManager::GetBackgroundVictim() const { |
| const size_t last = superblock_info_.GetTotalSections(); |
| // If the gc_type is GcType::kFgGc, we can select victim segments |
| // selected by background GC before. |
| // Those segments might have smaller valid blocks to be migrated. |
| size_t secno = 0; |
| while (!dirty_info_->victim_secmap.Scan(secno, last, false, &secno)) { |
| if (SecUsageCheck(static_cast<uint32_t>(secno))) { |
| ++secno; |
| continue; |
| } |
| return safemath::checked_cast<uint32_t>(secno); |
| } |
| return kNullSegNo; |
| } |
| |
| zx::result<uint32_t> SegmentManager::GetVictimByDefault(GcType gc_type, CursegType type, |
| AllocMode alloc_mode) { |
| std::lock_guard lock(seglist_lock_); |
| VictimSelPolicy policy = GetVictimSelPolicy(gc_type, type, alloc_mode); |
| |
| policy.min_segno = kNullSegNo; |
| policy.min_cost = GetMaxCost(policy); |
| |
| uint32_t nSearched = 0; |
| |
| if (policy.max_search == 0) { |
| return zx::error(ZX_ERR_UNAVAILABLE); |
| } |
| |
| if (policy.alloc_mode == AllocMode::kLFS && gc_type == GcType::kFgGc) { |
| uint32_t secno = GetBackgroundVictim(); |
| if (secno != kNullSegNo) { |
| dirty_info_->victim_secmap.ClearOne(secno); |
| policy.min_segno = safemath::checked_cast<uint32_t>(secno * superblock_info_.GetSegsPerSec()); |
| } |
| } |
| |
| auto &last_victim = last_victim_[static_cast<int>(policy.gc_mode)]; |
| auto gc_mode = static_cast<int>(policy.gc_mode); |
| if (policy.min_segno == kNullSegNo) { |
| block_t last_segment = TotalSegs(); |
| while (nSearched < policy.max_search) { |
| size_t dirty_seg; |
| if (policy.dirty_segmap->Scan(policy.offset, last_segment, false, &dirty_seg)) { |
| if (!last_victim) { |
| break; |
| } |
| last_segment = last_victim; |
| last_victim = 0; |
| policy.offset = 0; |
| continue; |
| } |
| uint32_t segno = safemath::checked_cast<uint32_t>(dirty_seg); |
| policy.offset = segno + policy.ofs_unit; |
| uint32_t secno = GetSecNo(segno); |
| |
| if (policy.ofs_unit > 1) { |
| policy.offset = fbl::round_down(policy.offset, policy.ofs_unit); |
| nSearched += |
| CountBits(*policy.dirty_segmap, policy.offset - policy.ofs_unit, policy.ofs_unit); |
| } else { |
| ++nSearched; |
| } |
| |
| if (SecUsageCheck(secno)) { |
| continue; |
| } |
| if (gc_type == GcType::kBgGc && dirty_info_->victim_secmap.GetOne(secno)) { |
| continue; |
| } |
| |
| size_t cost = GetGcCost(segno, policy); |
| |
| if (policy.min_cost > cost) { |
| policy.min_segno = segno; |
| policy.min_cost = cost; |
| } |
| |
| if (cost == GetMaxCost(policy)) { |
| continue; |
| } |
| |
| if (nSearched >= policy.max_search) { |
| // It has already checked all or |kMaxSearchLimit| of dirty segments. Set the last victim to |
| // |policy.offset| from which the next search will start to find victims. |
| last_victim_[static_cast<int>(gc_mode)] = |
| (safemath::CheckAdd<uint32_t>(segno, 1) % TotalSegs()).ValueOrDie(); |
| } |
| } |
| } |
| |
| if (policy.min_segno != kNullSegNo) { |
| if (policy.alloc_mode == AllocMode::kLFS) { |
| uint32_t secno = GetSecNo(policy.min_segno); |
| if (gc_type == GcType::kFgGc) { |
| cur_victim_sec_ = secno; |
| } else { |
| dirty_info_->victim_secmap.SetOne(secno); |
| } |
| } |
| return zx::ok( |
| safemath::checked_cast<uint32_t>(policy.min_segno - (policy.min_segno % policy.ofs_unit))); |
| } |
| |
| return zx::error(ZX_ERR_UNAVAILABLE); |
| } |
| |
| zx::result<uint32_t> SegmentManager::GetGcVictim(GcType gc_type, CursegType type) { |
| fs::SharedLock sentry_lock(sentry_lock_); |
| return GetVictimByDefault(gc_type, type, AllocMode::kLFS); |
| } |
| |
| bool SegmentManager::IsValidBlock(uint32_t segno, uint64_t offset) { |
| fs::SharedLock sentry_lock(sentry_lock_); |
| return sit_info_->sentries[segno].cur_valid_map.GetOne(ToMsbFirst(offset)); |
| } |
| |
| GcManager::GcManager(F2fs *fs) |
| : fs_(fs), |
| superblock_info_(fs->GetSuperblockInfo()), |
| segment_manager_(fs->GetSegmentManager()) {} |
| |
| zx::result<uint32_t> GcManager::Run() { |
| // For testing |
| if (disable_gc_for_test_) { |
| return zx::ok(0); |
| } |
| |
| if (superblock_info_.TestCpFlags(CpFlag::kCpErrorFlag)) { |
| return zx::error(ZX_ERR_BAD_STATE); |
| } |
| |
| if (!run_.try_acquire_for(std::chrono::seconds(kWriteTimeOut))) { |
| return zx::error(ZX_ERR_TIMED_OUT); |
| } |
| auto release = fit::defer([&] { run_.release(); }); |
| std::lock_guard gc_lock(f2fs::GetGlobalLock()); |
| |
| GcType gc_type = GcType::kBgGc; |
| uint32_t sec_freed = 0; |
| |
| // FG_GC must run when there is no space (e.g., HasNotEnoughFreeSecs() == true). |
| // If not, gc can compete with others (e.g., writeback) for victim Pages and space. |
| while (segment_manager_.HasNotEnoughFreeSecs()) { |
| // Stop writeback before gc. The writeback won't be invoked until gc acquires enough sections. |
| FlagAcquireGuard flag(&fs_->GetStopReclaimFlag()); |
| if (flag.IsAcquired()) { |
| ZX_ASSERT(fs_->WaitForWriteback().is_ok()); |
| } |
| |
| if (superblock_info_.TestCpFlags(CpFlag::kCpErrorFlag)) { |
| return zx::error(ZX_ERR_BAD_STATE); |
| } |
| // For example, if there are many prefree_segments below given threshold, we can make them |
| // free by checkpoint. Then, we secure free segments which doesn't need fggc any more. |
| if (segment_manager_.PrefreeSegments()) { |
| auto before = segment_manager_.FreeSections(); |
| if (zx_status_t ret = fs_->WriteCheckpoint(false, false); ret != ZX_OK) { |
| return zx::error(ret); |
| } |
| sec_freed = |
| (safemath::CheckSub<uint32_t>(segment_manager_.FreeSections(), before) + sec_freed) |
| .ValueOrDie(); |
| // After acquiring free sections, check if further gc is necessary. |
| continue; |
| } |
| |
| if (gc_type == GcType::kBgGc && segment_manager_.HasNotEnoughFreeSecs()) { |
| gc_type = GcType::kFgGc; |
| } |
| |
| auto segno_or = segment_manager_.GetGcVictim(gc_type, CursegType::kNoCheckType); |
| if (segno_or.is_error()) { |
| break; |
| } |
| if (auto err = DoGarbageCollect(*segno_or, gc_type); err != ZX_OK) { |
| return zx::error(err); |
| } |
| |
| if (gc_type == GcType::kFgGc) { |
| cur_victim_sec_ = kNullSecNo; |
| if (zx_status_t ret = fs_->WriteCheckpoint(false, false); ret != ZX_OK) { |
| return zx::error(ret); |
| } |
| ++sec_freed; |
| } |
| } |
| if (!sec_freed) { |
| return zx::error(ZX_ERR_UNAVAILABLE); |
| } |
| return zx::ok(sec_freed); |
| } |
| |
| zx_status_t GcManager::DoGarbageCollect(uint32_t start_segno, GcType gc_type) { |
| for (uint32_t i = 0; i < superblock_info_.GetSegsPerSec(); ++i) { |
| uint32_t segno = start_segno + i; |
| uint8_t type = IsDataSeg(static_cast<CursegType>(segment_manager_.GetSegmentEntry(segno).type)) |
| ? kSumTypeData |
| : kSumTypeNode; |
| |
| if (segment_manager_.CompareValidBlocks(0, segno, false)) { |
| continue; |
| } |
| |
| fbl::RefPtr<Page> sum_page; |
| { |
| LockedPage locked_sum_page; |
| segment_manager_.GetSumPage(segno, &locked_sum_page); |
| sum_page = locked_sum_page.release(); |
| } |
| |
| SummaryBlock *sum_blk = sum_page->GetAddress<SummaryBlock>(); |
| ZX_DEBUG_ASSERT(type == GetSumType((&sum_blk->footer))); |
| |
| if (zx_status_t status = (type == kSumTypeNode) ? GcNodeSegment(*sum_blk, segno, gc_type) |
| : GcDataSegment(*sum_blk, segno, gc_type); |
| status != ZX_OK) { |
| return status; |
| } |
| } |
| return ZX_OK; |
| } |
| |
| zx_status_t GcManager::GcNodeSegment(const SummaryBlock &sum_blk, uint32_t segno, GcType gc_type) { |
| const Summary *entry = sum_blk.entries; |
| for (block_t off = 0; off < superblock_info_.GetBlocksPerSeg(); ++off, ++entry) { |
| nid_t nid = CpuToLe(entry->nid); |
| |
| if (gc_type == GcType::kBgGc && segment_manager_.HasNotEnoughFreeSecs()) { |
| return ZX_ERR_BAD_STATE; |
| } |
| |
| if (!segment_manager_.IsValidBlock(segno, off)) { |
| continue; |
| } |
| |
| LockedPage node_page; |
| if (auto err = fs_->GetNodeManager().GetNodePage(nid, &node_page); err != ZX_OK) { |
| continue; |
| } |
| |
| NodeInfo ni; |
| fs_->GetNodeManager().GetNodeInfo(nid, ni); |
| if (ni.blk_addr != segment_manager_.StartBlock(segno) + off) { |
| continue; |
| } |
| |
| node_page->WaitOnWriteback(); |
| node_page.SetDirty(); |
| } |
| |
| return ZX_OK; |
| } |
| |
| zx::result<std::pair<nid_t, block_t>> GcManager::CheckDnode(const Summary &sum, block_t blkaddr) { |
| nid_t nid = LeToCpu(sum.nid); |
| uint16_t ofs_in_node = LeToCpu(sum.ofs_in_node); |
| |
| LockedPage node_page; |
| if (auto err = fs_->GetNodeManager().GetNodePage(nid, &node_page); err != ZX_OK) { |
| return zx::error(err); |
| } |
| |
| NodeInfo dnode_info; |
| fs_->GetNodeManager().GetNodeInfo(nid, dnode_info); |
| |
| if (sum.version != dnode_info.version) { |
| return zx::error(ZX_ERR_BAD_STATE); |
| } |
| |
| fs_->GetNodeManager().CheckNidRange(dnode_info.ino); |
| |
| fbl::RefPtr<VnodeF2fs> vnode; |
| if (zx_status_t err = VnodeF2fs::Vget(fs_, dnode_info.ino, &vnode); err != ZX_OK) { |
| return zx::error(err); |
| } |
| |
| auto start_bidx = node_page.GetPage<NodePage>().StartBidxOfNode(vnode->GetAddrsPerInode()); |
| block_t source_blkaddr = node_page.GetPage<NodePage>().GetBlockAddr(ofs_in_node); |
| |
| if (source_blkaddr != blkaddr) { |
| return zx::error(ZX_ERR_BAD_STATE); |
| } |
| return zx::ok(std::make_pair(dnode_info.ino, start_bidx)); |
| } |
| |
| zx_status_t GcManager::GcDataSegment(const SummaryBlock &sum_blk, unsigned int segno, |
| GcType gc_type) { |
| block_t start_addr = segment_manager_.StartBlock(segno); |
| const Summary *entry = sum_blk.entries; |
| PageList pages_to_disk; |
| for (block_t off = 0; off < superblock_info_.GetBlocksPerSeg(); ++off, ++entry) { |
| // stop BG_GC if there is not enough free sections. Or, stop GC if the section becomes fully |
| // valid caused by race condition along with SSR block allocation. |
| const uint32_t kBlocksPerSection = |
| superblock_info_.GetBlocksPerSeg() * superblock_info_.GetSegsPerSec(); |
| const block_t target_address = safemath::CheckAdd<block_t>(start_addr, off).ValueOrDie(); |
| if ((gc_type == GcType::kBgGc && segment_manager_.HasNotEnoughFreeSecs()) || |
| segment_manager_.CompareValidBlocks(kBlocksPerSection, segno, true)) { |
| return ZX_ERR_BAD_STATE; |
| } |
| |
| if (!segment_manager_.IsValidBlock(segno, off)) { |
| continue; |
| } |
| |
| auto dnode_result = CheckDnode(*entry, target_address); |
| if (dnode_result.is_error()) { |
| continue; |
| } |
| auto [ino, start_bidx] = dnode_result.value(); |
| |
| uint32_t ofs_in_node = LeToCpu(entry->ofs_in_node); |
| |
| fbl::RefPtr<VnodeF2fs> vnode; |
| if (auto err = VnodeF2fs::Vget(fs_, ino, &vnode); err != ZX_OK) { |
| continue; |
| } |
| |
| LockedPage data_page; |
| const size_t block_index = start_bidx + ofs_in_node; |
| // Keeps as long as dir vnodes use discardable vmos. |
| if (vnode->IsReg()) { |
| if (auto err = vnode->GrabCachePage(block_index, &data_page); err != ZX_OK) { |
| continue; |
| } |
| } else if (auto err = vnode->GetLockedDataPage(block_index, &data_page); err != ZX_OK) { |
| continue; |
| } |
| |
| data_page->WaitOnWriteback(); |
| pgoff_t offset = safemath::CheckMul(data_page->GetKey(), kBlockSize).ValueOrDie(); |
| // Ask kernel to dirty the vmo area for |data_page|. If the regarding pages are not present, we |
| // supply a vmo and dirty it again. |
| if (auto dirty_or = data_page.SetVmoDirty(); dirty_or.is_error()) { |
| vnode->VmoRead(offset, kBlockSize); |
| } |
| ZX_ASSERT(data_page.SetVmoDirty().is_ok()); |
| if (!vnode->IsValid()) { |
| // When victim blocks belongs to orphans, we load and keep them on paged_vmo until the orphans |
| // close or kernel reclaims the pages. |
| data_page.reset(); |
| vnode->TruncateHole(offset, offset + kBlockSize, false); |
| continue; |
| } |
| data_page.SetDirty(); |
| data_page->SetColdData(); |
| if (gc_type == GcType::kFgGc) { |
| block_t addr = vnode->GetBlockAddr(data_page); |
| if (addr == kNullAddr) { |
| continue; |
| } |
| ZX_DEBUG_ASSERT(addr != kNewAddr); |
| data_page->SetWriteback(); |
| pages_to_disk.push_back(data_page.release()); |
| } |
| } |
| if (!pages_to_disk.is_empty()) { |
| fs_->ScheduleWriter(nullptr, std::move(pages_to_disk)); |
| } |
| |
| if (gc_type == GcType::kFgGc && !segment_manager_.CompareValidBlocks(0, segno, false)) { |
| return ZX_ERR_BAD_STATE; |
| } |
| return ZX_OK; |
| } |
| |
| } // namespace f2fs |