| // 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. |
| |
| #ifndef F2FS_SEGMENT_H_ |
| #define F2FS_SEGMENT_H_ |
| |
| namespace f2fs { |
| |
| /* constant macro */ |
| constexpr uint32_t kNullSegNo = (uint32_t)(~0); |
| |
| /* during checkpoint, BioPrivate is used to synchronize the last bio */ |
| struct BioPrivate { |
| bool is_sync = false; |
| void *wait = nullptr; |
| }; |
| |
| /* |
| * indicate a block allocation direction: RIGHT and LEFT. |
| * RIGHT means allocating new sections towards the end of volume. |
| * LEFT means the opposite direction. |
| */ |
| enum class AllocDirection { kAllocRight = 0, kAllocLeft, }; |
| |
| /* |
| * In the VictimSelPolicy->alloc_mode, there are two block allocation modes. |
| * LFS writes data sequentially with cleaning operations. |
| * SSR (Slack Space Recycle) reuses obsolete space without cleaning operations. |
| */ |
| enum class AllocMode { kLFS = 0, kSSR }; |
| |
| /* |
| * In the VictimSelPolicy->gc_mode, there are two gc, aka cleaning, modes. |
| * GC_CB is based on cost-benefit algorithm. |
| * GC_GREEDY is based on greedy algorithm. |
| */ |
| enum class GcAlgorithm { kGcCb = 0, kGcGreedy }; |
| |
| /* |
| * BG_GC means the background cleaning job. |
| * FG_GC means the on-demand cleaning job. |
| */ |
| enum class GcType { kBgGc = 0, kFgGc }; |
| |
| /* 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 */ |
| }; |
| |
| struct SegEntry { |
| uint16_t valid_blocks = 0; /* # of valid blocks */ |
| uint8_t *cur_valid_map = nullptr; /* validity bitmap of blocks */ |
| /* |
| * # of valid blocks and the validity bitmap stored in the the last |
| * checkpoint pack. This information is used by the SSR mode. |
| */ |
| uint16_t ckpt_valid_blocks = 0; |
| uint8_t *ckpt_valid_map = nullptr; |
| uint8_t type = 0; /* segment type like CURSEG_XXX_TYPE */ |
| uint64_t mtime = 0; /* modification time of the segment */ |
| }; |
| |
| struct SecEntry { |
| uint32_t valid_blocks = 0; /* # of valid blocks in a section */ |
| }; |
| |
| struct SegmentAllocation { |
| void (*allocate_segment)(SbInfo *, int, bool) = nullptr; |
| }; |
| |
| struct SitInfo { |
| const SegmentAllocation *s_ops = nullptr; |
| |
| block_t sit_base_addr = 0; /* start block address of SIT area */ |
| block_t sit_blocks = 0; /* # of blocks used by SIT area */ |
| block_t written_valid_blocks = 0; /* # of valid blocks in main area */ |
| char *sit_bitmap = nullptr; /* SIT bitmap pointer */ |
| uint32_t bitmap_size = 0; /* SIT bitmap size */ |
| |
| uint64_t *dirty_sentries_bitmap = nullptr; /* bitmap for dirty sentries */ |
| uint32_t dirty_sentries = 0; /* # of dirty sentries */ |
| uint32_t sents_per_block = 0; /* # of SIT entries per block */ |
| mtx_t sentry_lock; /* to protect SIT cache */ |
| SegEntry *sentries = nullptr; /* SIT segment-level cache */ |
| SecEntry *sec_entries = nullptr; /* SIT section-level cache */ |
| |
| /* for cost-benefit algorithm in cleaning procedure */ |
| uint64_t elapsed_time = 0; /* elapsed time after mount */ |
| uint64_t mounted_time = 0; /* mount time */ |
| uint64_t min_mtime = 0; /* min. modification time */ |
| uint64_t max_mtime = 0; /* max. modification time */ |
| }; |
| |
| struct FreeSegmapInfo { |
| uint32_t start_segno = 0; /* start segment number logically */ |
| uint32_t free_segments = 0; /* # of free segments */ |
| uint32_t free_sections = 0; /* # of free sections */ |
| rwlock_t segmap_lock; /* free segmap lock */ |
| uint64_t *free_segmap = nullptr; /* free segment bitmap */ |
| uint64_t *free_secmap = nullptr; /* free section bitmap */ |
| }; |
| |
| /* Notice: The order of dirty type is same with CURSEG_XXX in f2fs.h */ |
| enum class DirtyType { |
| kDirtyHotData = 0, /* dirty segments assigned as hot data logs */ |
| kDirtyWarmData, /* dirty segments assigned as warm data logs */ |
| kDirtyColdData, /* dirty segments assigned as cold data logs */ |
| kDirtyHotNode, /* dirty segments assigned as hot node logs */ |
| kDirtyWarmNode, /* dirty segments assigned as warm node logs */ |
| kDirtyColdNode, /* dirty segments assigned as cold node logs */ |
| kDirty, /* to count # of dirty segments */ |
| kPre, /* to count # of entirely obsolete segments */ |
| kNrDirtytype |
| }; |
| |
| /* victim selection function for cleaning and SSR */ |
| struct VictimSelection { |
| int (*get_victim)(SbInfo *, uint32_t *, int, int, char) = nullptr; |
| }; |
| |
| struct DirtySeglistInfo { |
| const VictimSelection *v_ops = nullptr; /* victim selction operation */ |
| uint64_t *dirty_segmap[static_cast<int>(DirtyType::kNrDirtytype)] = {}; |
| mtx_t seglist_lock; /* lock for segment bitmaps */ |
| int nr_dirty[static_cast<int>(DirtyType::kNrDirtytype)] = {}; /* # of dirty segments */ |
| uint64_t *victim_segmap[2] = {}; /* BG_GC, FG_GC */ |
| }; |
| |
| /* for active log information */ |
| struct CursegInfo { |
| mtx_t curseg_mutex; /* lock for consistency */ |
| SummaryBlock *sum_blk = nullptr; /* cached summary block */ |
| uint8_t alloc_type = 0; /* current allocation type */ |
| uint32_t segno = 0; /* current segment number */ |
| uint16_t next_blkoff = 0; /* next block offset to write */ |
| uint32_t zone = 0; /* current zone number */ |
| uint32_t next_segno = 0; /* preallocated segment */ |
| }; |
| |
| /* V: Logical segment # in volume, R: Relative segment # in main area */ |
| inline uint32_t GetL2RSegNo(FreeSegmapInfo *free_i, uint32_t segno) { return (segno - free_i->start_segno); } |
| inline uint32_t GetR2LSegNo(FreeSegmapInfo *free_i, uint32_t segno) { return (segno + free_i->start_segno); } |
| |
| inline uint32_t IsDataSeg(CursegType t) { |
| return ((t == CursegType::kCursegHotData) || |
| (t == CursegType::kCursegColdData) || |
| (t == CursegType::kCursegWarmData)); |
| } |
| |
| inline uint32_t IsNodeSeg(CursegType t) { |
| return ((t == CursegType::kCursegHotNode) || (t == CursegType::kCursegColdNode) || (t == CursegType::kCursegWarmNode)); |
| } |
| |
| inline block_t StartBlock(SbInfo *sbi, uint32_t segno) { |
| return (GetSmInfo(sbi)->seg0_blkaddr + (GetR2LSegNo(GetFreeInfo(sbi), segno) << (sbi)->log_blocks_per_seg)); |
| } |
| inline block_t NextFreeBlkAddr(SbInfo *sbi, CursegInfo *curseg) { |
| return (StartBlock(sbi, curseg->segno) + curseg->next_blkoff); |
| } |
| |
| inline block_t MainBaseBlock(SbInfo *sbi) { return GetSmInfo(sbi)->main_blkaddr;} |
| |
| inline block_t GetSegOffFromSeg0(SbInfo *sbi, block_t blk_addr) { return blk_addr - GetSmInfo(sbi)->seg0_blkaddr; } |
| inline uint32_t GetSegNoFromSeg0(SbInfo *sbi, block_t blk_addr) { |
| return GetSegOffFromSeg0(sbi, blk_addr) >> sbi->log_blocks_per_seg; |
| } |
| |
| inline uint32_t GetSegNo(SbInfo *sbi, block_t blk_addr) { |
| return ((blk_addr == kNullAddr) || (blk_addr == kNewAddr)) ? kNullSegNo |
| : GetL2RSegNo(GetFreeInfo(sbi), GetSegNoFromSeg0(sbi, blk_addr)); |
| } |
| |
| inline uint32_t GetSecNo(SbInfo *sbi, uint32_t segno) { return segno / sbi->segs_per_sec; } |
| |
| inline uint32_t GetZoneNoFromSegNo(SbInfo *sbi, uint32_t segno) { |
| return (segno / sbi->segs_per_sec) / sbi->secs_per_zone; |
| } |
| |
| inline block_t GetSumBlock(SbInfo *sbi, uint32_t segno) { |
| return (sbi->sm_info->ssa_blkaddr) + segno; |
| } |
| |
| inline uint32_t SitEntryOffset(SitInfo *sit_i, uint32_t segno) { return segno % sit_i->sents_per_block; } |
| inline uint32_t SitBlockOffset(SitInfo *sit_i, uint32_t segno) { return segno / kSitEntryPerBlock; } |
| inline uint32_t StartSegNo(SitInfo *sit_i, uint32_t segno) { return SitBlockOffset(sit_i, segno) * kSitEntryPerBlock; } |
| inline uint32_t BitmapSize(uint32_t nr) { return BitsToLongs(nr) * sizeof(uint64_t); } |
| inline uint32_t TotalSegs(SbInfo *sbi) { return GetSmInfo(sbi)->main_segments; } |
| |
| class SegMgr { |
| public: |
| // Not copyable or moveable |
| SegMgr(const SegMgr &) = delete; |
| SegMgr &operator=(const SegMgr &) = delete; |
| SegMgr(SegMgr &&) = delete; |
| SegMgr &operator=(SegMgr &&) = delete; |
| |
| // TODO: Implement constructor |
| SegMgr(F2fs *fs); |
| |
| // TODO: Implement destructor |
| ~SegMgr() = default; |
| |
| // Static functions |
| static CursegInfo *CURSEG_I(SbInfo *sbi, CursegType type); |
| static int LookupJournalInCursum(SummaryBlock *sum, JournalType type, uint32_t val, |
| int alloc); |
| |
| // Public functions |
| zx_status_t BuildSegmentManager(); |
| void DestroySegmentManager(); |
| void RewriteNodePage(Page *page, Summary *sum, block_t old_blkaddr, |
| block_t new_blkaddr); |
| |
| private: |
| F2fs *fs_; |
| |
| public: |
| // Inline functions |
| SegEntry *GetSegEntry(uint32_t segno); |
| SecEntry *GetSecEntry(uint32_t segno); |
| uint32_t GetValidBlocks(uint32_t segno, int section); |
| void SegInfoFromRawSit(SegEntry *se, SitEntry *rs); |
| void SegInfoToRawSit(SegEntry *se, SitEntry *rs); |
| uint32_t FindNextInuse(FreeSegmapInfo *free_i, uint32_t max, uint32_t segno); |
| void SetFree(uint32_t segno); |
| void SetInuse(uint32_t segno); |
| void SetTestAndFree(uint32_t segno); |
| void SetTestAndInuse(uint32_t segno); |
| void GetSitBitmap(void *dst_addr); |
| #if 0 // porting needed |
| block_t WrittenBlockCount(); |
| #endif |
| uint32_t FreeSegments(); |
| int ReservedSegments(); |
| uint32_t FreeSections(); |
| uint32_t PrefreeSegments(); |
| uint32_t DirtySegments(); |
| int OverprovisionSegments(); |
| int OverprovisionSections(); |
| int ReservedSections(); |
| bool NeedSSR(); |
| int GetSsrSegment(CursegType type); |
| bool HasNotEnoughFreeSecs(); |
| uint32_t Utilization(); |
| bool NeedInplaceUpdate(VnodeF2fs *vnode); |
| uint32_t CursegSegno(int type); |
| uint8_t CursegAllocType(int type); |
| uint16_t CursegBlkoff(int type); |
| void CheckSegRange(uint32_t segno); |
| #if 0 // porting needed |
| void VerifyBlockAddr(block_t blk_addr); |
| #endif |
| void CheckBlockCount(int segno, SitEntry *raw_sit); |
| pgoff_t CurrentSitAddr(uint32_t start); |
| pgoff_t NextSitAddr(pgoff_t block_addr); |
| void SetToNextSit(SitInfo *sit_i, uint32_t start); |
| uint64_t GetMtime(); |
| void SetSummary(Summary *sum, nid_t nid, uint32_t ofs_in_node, |
| uint8_t version); |
| block_t StartSumBlock(); |
| block_t SumBlkAddr(int base, int type); |
| |
| // Functions |
| int NeedToFlush(); |
| void BalanceFs(); |
| void LocateDirtySegment(uint32_t segno, enum DirtyType dirty_type); |
| void RemoveDirtySegment(uint32_t segno, enum DirtyType dirty_type); |
| void LocateDirtySegment(uint32_t segno); |
| void SetPrefreeAsFreeSegments(); |
| void ClearPrefreeSegments(); |
| void MarkSitEntryDirty(uint32_t segno); |
| void SetSitEntryType(CursegType type, uint32_t segno, int modified); |
| void UpdateSitEntry(block_t blkaddr, int del); |
| void RefreshSitEntry(block_t old_blkaddr, block_t new_blkaddr); |
| void InvalidateBlocks(block_t addr); |
| void AddSumEntry(CursegType type, Summary *sum, uint16_t offset); |
| int NpagesForSummaryFlush(); |
| Page *GetSumPage(uint32_t segno); |
| void WriteSumPage(SummaryBlock *sum_blk, block_t blk_addr); |
| uint32_t CheckPrefreeSegments(int ofs_unit, CursegType type); |
| void GetNewSegment(uint32_t *newseg, bool new_sec, int dir); |
| void ResetCurseg(CursegType type, int modified); |
| void NewCurseg(CursegType type, bool new_sec); |
| void NextFreeBlkoff(CursegInfo *seg, block_t start); |
| void RefreshNextBlkoff(CursegInfo *seg); |
| void ChangeCurseg(CursegType type, bool reuse); |
| void AllocateSegmentByDefault(CursegType type, bool force); |
| void AllocateNewSegments(); |
| |
| #if 0 // porting needed |
| // const struct SegmentAllocation default_salloc_ops = { |
| // .allocate_segment = AllocateSegmentByDefault, |
| // }; |
| #endif |
| |
| #if 0 // porting needed |
| void EndIoWrite(bio *bio, int err); |
| bio *BioAlloc(block_device *bdev, sector_t first_sector, int nr_vecs, |
| gfp_t gfp_flags); |
| void DoSubmitBio(PageType type, bool sync); |
| #endif |
| void SubmitBio(PageType type, bool sync); |
| void SubmitWritePage(Page *page, block_t blk_addr, PageType type); |
| bool HasCursegSpace(CursegType type); |
| CursegType GetSegmentType2(Page *page, PageType p_type); |
| CursegType GetSegmentType4(Page *page, PageType p_type); |
| CursegType GetSegmentType6(Page *page, PageType p_type); |
| CursegType GetSegmentType(Page *page, PageType p_type); |
| void DoWritePage(Page *page, block_t old_blkaddr, block_t *new_blkaddr, Summary *sum, |
| PageType p_type); |
| zx_status_t WriteMetaPage(Page *page, WritebackControl *wbc); |
| void WriteNodePage(Page *page, uint32_t nid, block_t old_blkaddr, block_t *new_blkaddr); |
| void WriteDataPage(VnodeF2fs *vnode, Page *page, DnodeOfData *dn, block_t old_blkaddr, |
| block_t *new_blkaddr); |
| void RewriteDataPage(Page *page, block_t old_blk_addr); |
| void RecoverDataPage(Page *page, Summary *sum, block_t old_blkaddr, |
| block_t new_blkaddr); |
| |
| int ReadCompactedSummaries(); |
| int ReadNormalSummaries(int type); |
| int RestoreCursegSummaries(); |
| void WriteCompactedSummaries(block_t blkaddr); |
| void WriteNormalSummaries(block_t blkaddr, CursegType type); |
| void WriteDataSummaries(block_t start_blk); |
| void WriteNodeSummaries(block_t start_blk); |
| |
| Page *GetCurrentSitPage(uint32_t segno); |
| Page *GetNextSitPage(uint32_t start); |
| bool FlushSitsInJournal(); |
| void FlushSitEntries(); |
| |
| //////////////////////////////////////////// BUILD |
| /////////////////////////////////////////////////////////// |
| |
| zx_status_t BuildSitInfo(); |
| zx_status_t BuildFreeSegmap(); |
| zx_status_t BuildCurseg(); |
| void BuildSitEntries(); |
| void InitFreeSegmap(); |
| void InitDirtySegmap(); |
| zx_status_t InitVictimSegmap(); |
| zx_status_t BuildDirtySegmap(); |
| void InitMinMaxMtime(); |
| |
| void DiscardDirtySegmap(enum DirtyType dirty_type); |
| void ResetVictimSegmap(); |
| void DestroyVictimSegmap(); |
| void DestroyDirtySegmap(); |
| |
| void DestroyCurseg(); |
| void DestroyFreeSegmap(); |
| void DestroySitInfo(); |
| }; |
| |
| inline CursegInfo *SegMgr::CURSEG_I(SbInfo *sbi, CursegType type) { |
| return (CursegInfo *)(GetSmInfo(sbi)->curseg_array + static_cast<int>(type)); |
| } |
| |
| inline bool IsCurSeg(SbInfo *sbi, uint32_t segno) { |
| return ((segno == SegMgr::CURSEG_I(sbi, CursegType::kCursegHotData)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CursegType::kCursegWarmData)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CursegType::kCursegColdData)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CursegType::kCursegHotNode)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CursegType::kCursegWarmNode)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CursegType::kCursegColdNode)->segno)); |
| } |
| |
| inline bool IsCurSec(SbInfo *sbi, uint32_t secno) { |
| return ((secno == SegMgr::CURSEG_I(sbi, CursegType::kCursegHotData)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CursegType::kCursegWarmData)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CursegType::kCursegColdData)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CursegType::kCursegHotNode)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CursegType::kCursegWarmNode)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CursegType::kCursegColdNode)->segno / (sbi)->segs_per_sec)); |
| } |
| |
| } // namespace f2fs |
| |
| #endif // F2FS_SEGMENT_H_ |