segment.h

// 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 */
#define NULL_SEGNO ((unsigned int)(~0))

/* V: Logical segment # in volume, R: Relative segment # in main area */
#define GET_L2R_SEGNO(free_i, segno) (segno - free_i->start_segno)
#define GET_R2L_SEGNO(free_i, segno) (segno + free_i->start_segno)

#define IS_DATASEG(t) ((t == CURSEG_HOT_DATA) || (t == CURSEG_COLD_DATA) || (t == CURSEG_WARM_DATA))

#define IS_NODESEG(t) ((t == CURSEG_HOT_NODE) || (t == CURSEG_COLD_NODE) || (t == CURSEG_WARM_NODE))

#define IS_CURSEG(sbi, segno)                           \
  ((segno == CURSEG_I(sbi, CURSEG_HOT_DATA)->segno) ||  \
   (segno == CURSEG_I(sbi, CURSEG_WARM_DATA)->segno) || \
   (segno == CURSEG_I(sbi, CURSEG_COLD_DATA)->segno) || \
   (segno == CURSEG_I(sbi, CURSEG_HOT_NODE)->segno) ||  \
   (segno == CURSEG_I(sbi, CURSEG_WARM_NODE)->segno) || \
   (segno == CURSEG_I(sbi, CURSEG_COLD_NODE)->segno))

#define IS_CURSEC(sbi, secno)                                                 \
  ((secno == CURSEG_I(sbi, CURSEG_HOT_DATA)->segno / (sbi)->segs_per_sec) ||  \
   (secno == CURSEG_I(sbi, CURSEG_WARM_DATA)->segno / (sbi)->segs_per_sec) || \
   (secno == CURSEG_I(sbi, CURSEG_COLD_DATA)->segno / (sbi)->segs_per_sec) || \
   (secno == CURSEG_I(sbi, CURSEG_HOT_NODE)->segno / (sbi)->segs_per_sec) ||  \
   (secno == CURSEG_I(sbi, CURSEG_WARM_NODE)->segno / (sbi)->segs_per_sec) || \
   (secno == CURSEG_I(sbi, CURSEG_COLD_NODE)->segno / (sbi)->segs_per_sec))

#define START_BLOCK(sbi, segno) \
  (SM_I(sbi)->seg0_blkaddr + (GET_R2L_SEGNO(FREE_I(sbi), segno) << (sbi)->log_blocks_per_seg))
#define NEXT_FREE_BLKADDR(sbi, curseg) (START_BLOCK(sbi, curseg->segno) + curseg->next_blkoff)

#define MAIN_BASE_BLOCK(sbi) (SM_I(sbi)->main_blkaddr)

#define GET_SEGOFF_FROM_SEG0(sbi, blk_addr) ((blk_addr)-SM_I(sbi)->seg0_blkaddr)
#define GET_SEGNO_FROM_SEG0(sbi, blk_addr) \
  (GET_SEGOFF_FROM_SEG0(sbi, blk_addr) >> (sbi)->log_blocks_per_seg)
#define GET_SEGNO(sbi, blk_addr)                       \
  (((blk_addr == NULL_ADDR) || (blk_addr == NEW_ADDR)) \
       ? NULL_SEGNO                                    \
       : GET_L2R_SEGNO(FREE_I(sbi), GET_SEGNO_FROM_SEG0(sbi, blk_addr)))
#define GET_SECNO(sbi, segno) ((segno) / (sbi)->segs_per_sec)
#define GET_ZONENO_FROM_SEGNO(sbi, segno) ((segno / (sbi)->segs_per_sec) / (sbi)->secs_per_zone)

#define GET_SUM_BLOCK(sbi, segno) (((sbi)->sm_info->ssa_blkaddr) + segno)

#define SIT_ENTRY_OFFSET(sit_i, segno) (segno % (sit_i)->sents_per_block)
#define SIT_BLOCK_OFFSET(sit_i, segno) (segno / SIT_ENTRY_PER_BLOCK)
#define START_SEGNO(sit_i, segno) (SIT_BLOCK_OFFSET(sit_i, segno) * SIT_ENTRY_PER_BLOCK)
#define f2fs_bitmap_size(nr) (BITS_TO_LONGS(nr) * sizeof(unsigned long))
#define TOTAL_SEGS(sbi) (SM_I(sbi)->main_segments)

/* during checkpoint, bio_private is used to synchronize the last bio */
struct bio_private {
  ;
  bool is_sync;
  void *wait;
};

/*
 * indicate a block allocation direction: RIGHT and LEFT.
 * RIGHT means allocating new sections towards the end of volume.
 * LEFT means the opposite direction.
 */
enum { ALLOC_RIGHT = 0, ALLOC_LEFT };

/*
 * 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 { LFS = 0, SSR };

/*
 * 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 { GC_CB = 0, GC_GREEDY };

/*
 * BG_GC means the background cleaning job.
 * FG_GC means the on-demand cleaning job.
 */
enum { BG_GC = 0, FG_GC };

/* for a function parameter to select a victim segment */
struct victim_sel_policy {
  int alloc_mode;              /* LFS or SSR */
  int gc_mode;                 /* GC_CB or GC_GREEDY */
  unsigned long *dirty_segmap; /* dirty segment bitmap */
  unsigned int offset;         /* last scanned bitmap offset */
  unsigned int ofs_unit;       /* bitmap search unit */
  unsigned int min_cost;       /* minimum cost */
  unsigned int min_segno;      /* segment # having min. cost */
};

struct seg_entry {
  unsigned short valid_blocks;  /* # of valid blocks */
  unsigned char *cur_valid_map; /* 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.
   */
  unsigned short ckpt_valid_blocks;
  unsigned char *ckpt_valid_map;
  unsigned char type;       /* segment type like CURSEG_XXX_TYPE */
  unsigned long long mtime; /* modification time of the segment */
};

struct sec_entry {
  unsigned int valid_blocks; /* # of valid blocks in a section */
};

struct segment_allocation {
  void (*allocate_segment)(struct f2fs_sb_info *, int, bool);
};

struct sit_info {
  const struct segment_allocation *s_ops;

  block_t sit_base_addr;        /* start block address of SIT area */
  block_t sit_blocks;           /* # of blocks used by SIT area */
  block_t written_valid_blocks; /* # of valid blocks in main area */
  char *sit_bitmap;             /* SIT bitmap pointer */
  unsigned int bitmap_size;     /* SIT bitmap size */

  unsigned long *dirty_sentries_bitmap; /* bitmap for dirty sentries */
  unsigned int dirty_sentries;          /* # of dirty sentries */
  unsigned int sents_per_block;         /* # of SIT entries per block */
  mtx_t sentry_lock;                    /* to protect SIT cache */
  struct seg_entry *sentries;           /* SIT segment-level cache */
  struct sec_entry *sec_entries;        /* SIT section-level cache */

  /* for cost-benefit algorithm in cleaning procedure */
  unsigned long long elapsed_time; /* elapsed time after mount */
  unsigned long long mounted_time; /* mount time */
  unsigned long long min_mtime;    /* min. modification time */
  unsigned long long max_mtime;    /* max. modification time */
};

struct free_segmap_info {
  unsigned int start_segno;   /* start segment number logically */
  unsigned int free_segments; /* # of free segments */
  unsigned int free_sections; /* # of free sections */
  rwlock_t segmap_lock;       /* free segmap lock */
  unsigned long *free_segmap; /* free segment bitmap */
  unsigned long *free_secmap; /* free section bitmap */
};

/* Notice: The order of dirty type is same with CURSEG_XXX in f2fs.h */
enum dirty_type {
  DIRTY_HOT_DATA,  /* dirty segments assigned as hot data logs */
  DIRTY_WARM_DATA, /* dirty segments assigned as warm data logs */
  DIRTY_COLD_DATA, /* dirty segments assigned as cold data logs */
  DIRTY_HOT_NODE,  /* dirty segments assigned as hot node logs */
  DIRTY_WARM_NODE, /* dirty segments assigned as warm node logs */
  DIRTY_COLD_NODE, /* dirty segments assigned as cold node logs */
  DIRTY,           /* to count # of dirty segments */
  PRE,             /* to count # of entirely obsolete segments */
  NR_DIRTY_TYPE
};

struct dirty_seglist_info {
  const struct victim_selection *v_ops; /* victim selction operation */
  unsigned long *dirty_segmap[NR_DIRTY_TYPE];
  mtx_t seglist_lock;              /* lock for segment bitmaps */
  int nr_dirty[NR_DIRTY_TYPE];     /* # of dirty segments */
  unsigned long *victim_segmap[2]; /* BG_GC, FG_GC */
};

/* victim selection function for cleaning and SSR */
struct victim_selection {
  int (*get_victim)(struct f2fs_sb_info *, unsigned int *, int, int, char);
};

/* for active log information */
struct curseg_info {
  mtx_t curseg_mutex;                 /* lock for consistency */
  struct f2fs_summary_block *sum_blk; /* cached summary block */
  unsigned char alloc_type;           /* current allocation type */
  unsigned int segno;                 /* current segment number */
  unsigned short next_blkoff;         /* next block offset to write */
  unsigned int zone;                  /* current zone number */
  unsigned int next_segno;            /* preallocated segment */
};

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 struct curseg_info *CURSEG_I(f2fs_sb_info *sbi, int type);
  static int LookupJournalInCursum(struct f2fs_summary_block *sum, int type, unsigned int val,
                                   int alloc);

  // Public functions
  zx_status_t BuildSegmentManager();
  void DestroySegmentManager();
  void RewriteNodePage(Page *page, struct f2fs_summary *sum, block_t old_blkaddr,
                       block_t new_blkaddr);

 private:
  F2fs *fs_;

 public:
  // Inline functions
  struct seg_entry *GetSegEntry(unsigned int segno);
  struct sec_entry *GetSecEntry(unsigned int segno);
  unsigned int GetValidBlocks(unsigned int segno, int section);
  void SegInfoFromRawSit(struct seg_entry *se, struct f2fs_sit_entry *rs);
  void SegInfoToRawSit(struct seg_entry *se, struct f2fs_sit_entry *rs);
  unsigned int FindNextInuse(struct free_segmap_info *free_i, unsigned int max, unsigned int segno);
  void __SetFree(unsigned int segno);
  void __SetInuse(unsigned int segno);
  void __SetTestAndFree(unsigned int segno);
  void __SetTestAndInuse(unsigned int segno);
  void GetSitBitmap(void *dst_addr);
#if 0 // porting needed
  block_t WrittenBlockCount();
#endif
  unsigned int FreeSegments();
  int ReservedSegments();
  unsigned int FreeSections();
  unsigned int PrefreeSegments();
  unsigned int DirtySegments();
  int OverprovisionSegments();
  int OverprovisionSections();
  int ReservedSections();
  bool NeedSSR();
  int GetSsrSegment(int type);
  bool HasNotEnoughFreeSecs();
  int Utilization();
  bool NeedInplaceUpdate(VnodeF2fs *vnode);
  unsigned int CursegSegno(int type);
  unsigned char CursegAllocType(int type);
  unsigned short CursegBlkoff(int type);
  void CheckSegRange(unsigned int segno);
  #if 0 // porting needed
  void VerifyBlockAddr(block_t blk_addr);
  #endif
  void CheckBlockCount(int segno, struct f2fs_sit_entry *raw_sit);
  pgoff_t CurrentSitAddr(unsigned int start);
  pgoff_t NextSitAddr(pgoff_t block_addr);
  void SetToNextSit(struct sit_info *sit_i, unsigned int start);
  unsigned long long GetMtime();
  void SetSummary(struct f2fs_summary *sum, nid_t nid, unsigned int ofs_in_node,
                  unsigned char version);
  block_t StartSumBlock();
  block_t SumBlkAddr(int base, int type);

  // Functions
  int NeedToFlush();
  void F2fsBalanceFs();
  void __LocateDirtySegment(unsigned int segno, enum dirty_type dirty_type);
  void __RemoveDirtySegment(unsigned int segno, enum dirty_type dirty_type);
  void LocateDirtySegment(unsigned int segno);
  void SetPrefreeAsFreeSegments();
  void ClearPrefreeSegments();
  void __MarkSitEntryDirty(unsigned int segno);
  void __SetSitEntryType(int type, unsigned int 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, struct f2fs_summary *sum, unsigned short offset);
  int NpagesForSummaryFlush();
  Page *GetSumPage(unsigned int segno);
  void WriteSumPage(struct f2fs_summary_block *sum_blk, block_t blk_addr);
  unsigned int CheckPrefreeSegments(int ofs_unit, int type);
  void GetNewSegment(unsigned int *newseg, bool new_sec, int dir);
  void ResetCurseg(int type, int modified);
  void NewCurseg(int type, bool new_sec);
  void __NextFreeBlkoff(struct curseg_info *seg, block_t start);
  void __RefreshNextBlkoff(struct 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(struct bio *bio, int err);
  struct bio *F2fsBioAlloc(struct 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, struct f2fs_summary *sum,
                   enum page_type p_type);
  int WriteMetaPage(Page *page, struct writeback_control *wbc);
  void WriteNodePage(Page *page, unsigned int nid, block_t old_blkaddr, block_t *new_blkaddr);
  void WriteDataPage(VnodeF2fs *vnode, Page *page, struct 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, struct 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(unsigned int segno);
  Page *GetNextSitPage(unsigned int start);
  bool FlushSitsInJournal();
  void FlushSitEntries();

  //////////////////////////////////////////// BUILD
  ///////////////////////////////////////////////////////////

  int BuildSitInfo();
  int BuildFreeSegmap();
  int BuildCurseg();
  void BuildSitEntries();
  void InitFreeSegmap();
  void InitDirtySegmap();
  int InitVictimSegmap();
  int BuildDirtySegmap();
  void InitMinMaxMtime();

  void DiscardDirtySegmap(enum dirty_type dirty_type);
  void ResetVictimSegmap();
  void DestroyVictimSegmap();
  void DestroyDirtySegmap();

  void DestroyCurseg();
  void DestroyFreeSegmap();
  void DestroySitInfo();
};

inline struct curseg_info *SegMgr::CURSEG_I(f2fs_sb_info *sbi, int type) {
  return (struct curseg_info *)(SM_I(sbi)->curseg_array + type);
}

}  // namespace f2fs

#endif  // F2FS_SEGMENT_H_