| // 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_ |
| |
| #include "zircon/types.h" |
| namespace f2fs { |
| |
| /* constant macro */ |
| constexpr uint32_t kNullSegNo = (uint32_t)(~0); |
| |
| /* during checkpoint, bio_private is used to synchronize the last bio */ |
| struct bio_private { |
| 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 victim_sel_policy->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 victim_sel_policy->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 victim_sel_policy { |
| 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 seg_entry { |
| 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 sec_entry { |
| uint32_t valid_blocks = 0; /* # of valid blocks in a section */ |
| }; |
| |
| struct segment_allocation { |
| void (*allocate_segment)(f2fs_sb_info *, int, bool) = nullptr; |
| }; |
| |
| struct sit_info { |
| const segment_allocation *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 */ |
| seg_entry *sentries = nullptr; /* SIT segment-level cache */ |
| sec_entry *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 free_segmap_info { |
| 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 |
| }; |
| |
| struct dirty_seglist_info { |
| const struct victim_selection *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 */ |
| }; |
| |
| /* victim selection function for cleaning and SSR */ |
| struct victim_selection { |
| int (*get_victim)(f2fs_sb_info *, uint32_t *, int, int, char) = nullptr; |
| }; |
| |
| /* for active log information */ |
| struct curseg_info { |
| mtx_t curseg_mutex; /* lock for consistency */ |
| f2fs_summary_block *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(free_segmap_info *free_i, uint32_t segno) { return (segno - free_i->start_segno); } |
| inline uint32_t GetR2LSegNo(free_segmap_info *free_i, uint32_t segno) { return (segno + free_i->start_segno); } |
| |
| inline uint32_t IsDataSeg(uint32_t t) { |
| return ((t == CURSEG_HOT_DATA) || (t == CURSEG_COLD_DATA) || (t == CURSEG_WARM_DATA)); |
| } |
| |
| inline uint32_t IsNodeSeg(uint32_t t) { |
| return ((t == CURSEG_HOT_NODE) || (t == CURSEG_COLD_NODE) || (t == CURSEG_WARM_NODE)); |
| } |
| |
| inline block_t StartBlock(f2fs_sb_info *sbi, uint32_t segno) { |
| return (SM_I(sbi)->seg0_blkaddr + (GetR2LSegNo(FREE_I(sbi), segno) << (sbi)->log_blocks_per_seg)); |
| } |
| inline block_t NextFreeBlkAddr(f2fs_sb_info *sbi, curseg_info *curseg) { |
| return (StartBlock(sbi, curseg->segno) + curseg->next_blkoff); |
| } |
| |
| inline block_t MainBaseBlock(f2fs_sb_info *sbi) { return SM_I(sbi)->main_blkaddr;} |
| |
| inline block_t GetSegOffFromSeg0(f2fs_sb_info *sbi, block_t blk_addr) { return blk_addr - SM_I(sbi)->seg0_blkaddr; } |
| inline uint32_t GetSegNoFromSeg0(f2fs_sb_info *sbi, block_t blk_addr) { |
| return GetSegOffFromSeg0(sbi, blk_addr) >> sbi->log_blocks_per_seg; |
| } |
| |
| inline uint32_t GetSegNo(f2fs_sb_info *sbi, block_t blk_addr) { |
| return ((blk_addr == NULL_ADDR) || (blk_addr == NEW_ADDR)) ? kNullSegNo |
| : GetL2RSegNo(FREE_I(sbi), GetSegNoFromSeg0(sbi, blk_addr)); |
| } |
| |
| inline uint32_t GetSecNo(f2fs_sb_info *sbi, uint32_t segno) { return segno / sbi->segs_per_sec; } |
| |
| inline uint32_t GetZoneNoFromSegNo(f2fs_sb_info *sbi, uint32_t segno) { |
| return (segno / sbi->segs_per_sec) / sbi->secs_per_zone; |
| } |
| |
| inline block_t GetSumBlock(f2fs_sb_info *sbi, uint32_t segno) { |
| return (sbi->sm_info->ssa_blkaddr) + segno; |
| } |
| |
| inline uint32_t SitEntryOffset(sit_info *sit_i, uint32_t segno) { return segno % sit_i->sents_per_block; } |
| inline uint32_t SitBlockOffset(sit_info *sit_i, uint32_t segno) { return segno / SIT_ENTRY_PER_BLOCK; } |
| inline uint32_t StartSegNo(sit_info *sit_i, uint32_t segno) { return SitBlockOffset(sit_i, segno) * SIT_ENTRY_PER_BLOCK; } |
| inline uint32_t BitmapSize(uint32_t nr) { return BitsToLongs(nr) * sizeof(uint64_t); } |
| inline uint32_t TotalSegs(f2fs_sb_info *sbi) { return SM_I(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 curseg_info *CURSEG_I(f2fs_sb_info *sbi, int type); |
| static int LookupJournalInCursum(f2fs_summary_block *sum, int type, uint32_t val, |
| int alloc); |
| |
| // Public functions |
| zx_status_t BuildSegmentManager(); |
| void DestroySegmentManager(); |
| void RewriteNodePage(Page *page, f2fs_summary *sum, block_t old_blkaddr, |
| block_t new_blkaddr); |
| |
| private: |
| F2fs *fs_; |
| |
| public: |
| // Inline functions |
| seg_entry *GetSegEntry(uint32_t segno); |
| sec_entry *GetSecEntry(uint32_t segno); |
| uint32_t GetValidBlocks(uint32_t segno, int section); |
| void SegInfoFromRawSit(seg_entry *se, f2fs_sit_entry *rs); |
| void SegInfoToRawSit(seg_entry *se, f2fs_sit_entry *rs); |
| uint32_t FindNextInuse(free_segmap_info *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(int 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, f2fs_sit_entry *raw_sit); |
| pgoff_t CurrentSitAddr(uint32_t start); |
| pgoff_t NextSitAddr(pgoff_t block_addr); |
| void SetToNextSit(sit_info *sit_i, uint32_t start); |
| uint64_t GetMtime(); |
| void SetSummary(f2fs_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 F2fsBalanceFs(); |
| 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(int 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(int type, f2fs_summary *sum, uint16_t offset); |
| int NpagesForSummaryFlush(); |
| Page *GetSumPage(uint32_t segno); |
| void WriteSumPage(f2fs_summary_block *sum_blk, block_t blk_addr); |
| uint32_t CheckPrefreeSegments(int ofs_unit, int type); |
| void GetNewSegment(uint32_t *newseg, bool new_sec, int dir); |
| void ResetCurseg(int type, int modified); |
| void NewCurseg(int type, bool new_sec); |
| void __NextFreeBlkoff(curseg_info *seg, block_t start); |
| void __RefreshNextBlkoff(curseg_info *seg); |
| void ChangeCurseg(int type, bool reuse); |
| void AllocateSegmentByDefault(int type, bool force); |
| void AllocateNewSegments(); |
| |
| #if 0 // porting needed |
| // const struct segment_allocation default_salloc_ops = { |
| // .allocate_segment = AllocateSegmentByDefault, |
| // }; |
| #endif |
| |
| #if 0 // porting needed |
| void F2fsEndIoWrite(bio *bio, int err); |
| bio *F2fsBioAlloc(block_device *bdev, sector_t first_sector, int nr_vecs, |
| gfp_t gfp_flags); |
| void DoSubmitBio(enum page_type type, bool sync); |
| #endif |
| void F2fsSubmitBio(enum page_type type, bool sync); |
| void SubmitWritePage(Page *page, block_t blk_addr, enum page_type type); |
| bool __HasCursegSpace(int type); |
| int __GetSegmentType2(Page *page, enum page_type p_type); |
| int __GetSegmentType4(Page *page, enum page_type p_type); |
| int __GetSegmentType6(Page *page, enum page_type p_type); |
| int __GetSegmentType(Page *page, enum page_type p_type); |
| void DoWritePage(Page *page, block_t old_blkaddr, block_t *new_blkaddr, f2fs_summary *sum, |
| enum page_type 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, dnode_of_data *dn, block_t old_blkaddr, |
| block_t *new_blkaddr); |
| void RewriteDataPage(Page *page, block_t old_blk_addr); |
| void RecoverDataPage(Page *page, f2fs_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, int 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 curseg_info *SegMgr::CURSEG_I(f2fs_sb_info *sbi, int type) { |
| return (curseg_info *)(SM_I(sbi)->curseg_array + type); |
| } |
| |
| inline bool IsCurSeg(f2fs_sb_info *sbi, uint32_t segno) { |
| return ((segno == SegMgr::CURSEG_I(sbi, CURSEG_HOT_DATA)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CURSEG_WARM_DATA)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CURSEG_COLD_DATA)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CURSEG_HOT_NODE)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CURSEG_WARM_NODE)->segno) || |
| (segno == SegMgr::CURSEG_I(sbi, CURSEG_COLD_NODE)->segno)); |
| } |
| |
| inline bool IsCurSec(f2fs_sb_info *sbi, uint32_t secno) { |
| return ((secno == SegMgr::CURSEG_I(sbi, CURSEG_HOT_DATA)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CURSEG_WARM_DATA)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CURSEG_COLD_DATA)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CURSEG_HOT_NODE)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CURSEG_WARM_NODE)->segno / (sbi)->segs_per_sec) || |
| (secno == SegMgr::CURSEG_I(sbi, CURSEG_COLD_NODE)->segno / (sbi)->segs_per_sec)); |
| } |
| |
| } // namespace f2fs |
| |
| #endif // F2FS_SEGMENT_H_ |