src/storage/f2fs/node.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 SRC_STORAGE_F2FS_NODE_H_
#define SRC_STORAGE_F2FS_NODE_H_

namespace f2fs {

// start node id of a node block dedicated to the given node id
inline uint32_t StartNid(uint32_t nid) { return (nid / kNatEntryPerBlock) * kNatEntryPerBlock; }

// node block offset on the NAT area dedicated to the given start node id
inline uint64_t NatBlockOffset(uint32_t start_nid) { return start_nid / kNatEntryPerBlock; }

// # of pages to perform readahead before building free nids
constexpr int kFreeNidPages = 4;

// maximum # of free node ids to produce during build_free_nids
constexpr int kMaxFreeNids = kNatEntryPerBlock * kFreeNidPages;

// maximum readahead size for node during getting data blocks
constexpr int kMaxRaNode = 128;

// maximum cached nat entries to manage memory footprint
constexpr uint32_t kNmWoutThreshold = 64 * kNatEntryPerBlock;

// vector size for gang look-up from nat cache that consists of radix tree
constexpr uint32_t kNatvecSize = 64;

// For directory operation
constexpr size_t kNodeDir1Block = kAddrsPerInode + 1;
constexpr size_t kNodeDir2Block = kAddrsPerInode + 2;
constexpr size_t kNodeInd1Block = kAddrsPerInode + 3;
constexpr size_t kNodeInd2Block = kAddrsPerInode + 4;
constexpr size_t kNodeDIndBlock = kAddrsPerInode + 5;

// maximum node block level of data block
constexpr uint32_t kMaxNodeBlockLevel = 4;

// For node information
struct NodeInfo {
  nid_t nid = 0;         // node id
  nid_t ino = 0;         // inode number of the node's owner
  block_t blk_addr = 0;  // block address of the node
  uint8_t version = 0;   // version of the node
};

class NatEntry : public fbl::WAVLTreeContainable<std::unique_ptr<NatEntry>>,
                 public fbl::DoublyLinkedListable<NatEntry *> {
 public:
  NatEntry() = default;
  NatEntry(const NatEntry &) = delete;
  NatEntry &operator=(const NatEntry &) = delete;
  NatEntry(const NatEntry &&) = delete;
  NatEntry &operator=(const NatEntry &&) = delete;

  const NodeInfo &GetNodeInfo() { return ni_; }
  void SetNodeInfo(const NodeInfo &value) { ni_ = value; }

  bool IsCheckpointed() const { return checkpointed_; }
  void SetCheckpointed() { checkpointed_ = true; }
  void ClearCheckpointed() { checkpointed_ = false; }
  uint32_t GetNid() const { return ni_.nid; }
  void SetNid(const nid_t value) { ni_.nid = value; }
  block_t GetBlockAddress() { return ni_.blk_addr; }
  void SetBlockAddress(const block_t value) { ni_.blk_addr = value; }
  uint32_t GetIno() { return ni_.ino; }
  void SetIno(const nid_t value) { ni_.ino = value; }
  uint8_t GetVersion() { return ni_.version; }
  void SetVersion(const uint8_t value) { ni_.version = value; }
  ino_t GetKey() const { return ni_.nid; }

 private:
  bool checkpointed_ = false;  // whether it is checkpointed or not
  NodeInfo ni_;                // in-memory node information
};

inline uint8_t IncNodeVersion(uint8_t version) { return ++version; }

// For free nid mangement
enum class NidState {
  kNidNew = 0,  // newly added to free nid list
  kNidAlloc,    // it is allocated
};

struct FreeNid {
  list_node_t list;  // for free node id list
  nid_t nid = 0;     // node id
  int state = 0;     // in use or not: kNidNew or kNidAlloc
};

class MapTester;

class NodeManager {
 public:
  // Not copyable or moveable
  NodeManager(const NodeManager &) = delete;
  NodeManager &operator=(const NodeManager &) = delete;
  NodeManager(NodeManager &&) = delete;
  NodeManager &operator=(NodeManager &&) = delete;

  NodeManager(F2fs *fs);

  zx_status_t NextFreeNid(nid_t *nid);
  void NodeInfoFromRawNat(NodeInfo &ni, RawNatEntry &raw_ne);
  zx_status_t BuildNodeManager();
  void DestroyNodeManager();
  zx_status_t ReadNodePage(LockedPage &page, nid_t nid, int type);
  zx_status_t GetNodePage(nid_t nid, LockedPage *out);

  // If an unassigned node page is encountered while following the node path, a new node page is
  // assigned. Caller should acquire LockType:kFileOp.
  zx_status_t GetLockedDnodePage(VnodeF2fs &vnode, pgoff_t index, LockedPage *out);

  // Read-only mode of GetLockedDnodePage().
  zx_status_t FindLockedDnodePage(VnodeF2fs &vnode, pgoff_t index, LockedPage *out);

  zx::status<uint32_t> GetOfsInDnode(VnodeF2fs &vnode, pgoff_t index);

  zx_status_t RestoreNodeSummary(uint32_t segno, SummaryBlock &sum);

  static bool IsColdFile(VnodeF2fs &vnode);

  void GetNodeInfo(nid_t nid, NodeInfo &out);

  // It flushes all dirty node Pages that meet |operation|.if_page.
  // It also removes dirty vnodes from the dirty list when there is no dirty Page for their vnodes
  // and data. To ensure there is no access to the vnodes, it is called with LockType::kFileOp held
  // during ckpt. This way guarantees that RecycleNode() for valid vnodes executes only at ckpt
  // time.
  pgoff_t SyncNodePages(WritebackOperation &operation);
  pgoff_t FsyncNodePages(VnodeF2fs &vnode);

  bool AllocNid(nid_t &out);
  void AllocNidFailed(nid_t nid);
  void AllocNidDone(nid_t nid);
  zx_status_t TruncateInodeBlocks(VnodeF2fs &vnode, pgoff_t from);

  // Caller should acquire LockType:kFileOp.
  zx_status_t RemoveInodePage(VnodeF2fs *vnode);
  // Caller should acquire LockType:kFileOp.
  zx_status_t NewInodePage(Dir *parent, VnodeF2fs *child);

  bool IsCheckpointedNode(nid_t nid);

  void DecValidNodeCount(VnodeF2fs *vnode, uint32_t count);
  bool FlushNatsInJournal();
  void FlushNatEntries();

  int F2fsWriteNodePage(LockedPage &page, bool is_reclaim = false);
  int F2fsWriteNodePages(VnodeF2fs &vnode, bool is_reclaim = false);

  zx_status_t RecoverInodePage(NodePage &page);

  // Check whether the given nid is within node id range.
  void CheckNidRange(const nid_t &nid) { ZX_ASSERT(nid < max_nid_); }

  // members for fsck and unit tests
  NodeManager(SuperblockInfo *sb);
  void SetMaxNid(const nid_t value) { max_nid_ = value; }
  nid_t GetMaxNid() const { return max_nid_; }
  void SetNatAddress(const block_t value) { nat_blkaddr_ = value; }
  block_t GetNatAddress() { return nat_blkaddr_; }
  void SetFirstScanNid(const nid_t value) { init_scan_nid_ = value; }
  nid_t GetFirstScanNid() const { return init_scan_nid_; }
  void SetNextScanNid(const nid_t value) { next_scan_nid_ = value; }
  nid_t GetNextScanNid() const { return next_scan_nid_; }
  nid_t GetNatCount() const { return nat_entries_count_; }
  nid_t GetFreeNidCount() const { return free_nid_count_; }
  zx_status_t AllocNatBitmap(const int size) {
    nat_bitmap_size_ = size;
    nat_bitmap_ = std::make_unique<uint8_t[]>(nat_bitmap_size_);
    memset(nat_bitmap_.get(), 0, nat_bitmap_size_);
    return ZX_OK;
  }
  void SetNatBitmap(const uint8_t *bitmap) { memcpy(nat_bitmap_.get(), bitmap, nat_bitmap_size_); }
  uint8_t *GetNatBitmap() const { return nat_bitmap_.get(); }
  void GetNatBitmap(void *addr);

  SuperblockInfo &GetSuperblockInfo();

 private:
  friend class MapTester;
  bool IncValidNodeCount(VnodeF2fs *vnode, uint32_t count);

  pgoff_t CurrentNatAddr(nid_t start);
  bool IsUpdatedNatPage(nid_t start);
  pgoff_t NextNatAddr(pgoff_t block_addr);
  void SetToNextNat(nid_t start_nid);

  void GetCurrentNatPage(nid_t nid, LockedPage *out);
  void GetNextNatPage(nid_t nid, LockedPage *out);
  void RaNatPages(nid_t nid);

  void SetNatCacheDirty(NatEntry &ne) __TA_REQUIRES(nat_tree_lock_);
  void ClearNatCacheDirty(NatEntry &ne) __TA_REQUIRES(nat_tree_lock_);
  NatEntry *LookupNatCache(nid_t n) __TA_REQUIRES_SHARED(nat_tree_lock_);
  uint32_t GangLookupNatCache(uint32_t nr, NatEntry **ep) __TA_REQUIRES_SHARED(nat_tree_lock_);
  void DelFromNatCache(NatEntry &entry) __TA_REQUIRES_SHARED(nat_tree_lock_);
  NatEntry *GrabNatEntry(nid_t nid) __TA_REQUIRES_SHARED(nat_tree_lock_);
  void CacheNatEntry(nid_t nid, RawNatEntry &ne);
  void SetNodeAddr(NodeInfo &ni, block_t new_blkaddr);
  int TryToFreeNats(int nr_shrink);

  zx::status<int32_t> GetNodePath(VnodeF2fs &vnode, pgoff_t block,
                                  int32_t (&offset)[kMaxNodeBlockLevel],
                                  uint32_t (&noffset)[kMaxNodeBlockLevel]);

  // Caller should ensure node_page is locked.
  void TruncateNode(VnodeF2fs &vnode, nid_t nid, NodePage &node_page);
  zx::status<uint32_t> TruncateDnode(VnodeF2fs &vnode, nid_t nid);
  zx::status<uint32_t> TruncateNodes(VnodeF2fs &vnode, nid_t start_nid, uint32_t nofs, int32_t ofs,
                                     int32_t depth);
  zx_status_t TruncatePartialNodes(VnodeF2fs &vnode, const Inode &ri,
                                   const int32_t (&offset)[kMaxNodeBlockLevel], int32_t depth);
  zx_status_t NewNodePage(VnodeF2fs &vnode, nid_t nid, uint32_t ofs, LockedPage *out);

#if 0  // Use xxColdxx and RA when gc impl.
  static int IsColdData(Page &page);
  static void ClearColdData(Page &page);
  void SetColdData(Page &page);
  Page *GetNodePageRa(Page *parent, int start);
  void RaNodePage(nid_t nid);
#endif

  FreeNid *LookupFreeNidList(nid_t n);
  void DelFromFreeNidList(FreeNid *i);
  int AddFreeNid(nid_t nid);
  void RemoveFreeNid(nid_t nid);
  int ScanNatPage(Page &nat_page, nid_t start_nid);
  void BuildFreeNids();
  zx_status_t InitNodeManager();

  F2fs *fs_ = nullptr;
  SuperblockInfo *superblock_info_ = nullptr;
  block_t nat_blkaddr_ = 0;   // starting block address of NAT
  nid_t max_nid_ = 0;         // the maximum number of node ids
  nid_t init_scan_nid_ = 0;   // the first nid to be scanned
  nid_t next_scan_nid_ = 0;   // the next nid to be scanned
  nid_t free_nid_count_ = 0;  // the number of free node id

  fs::SharedMutex nat_tree_lock_;   // protect nat_tree_lock
  uint32_t nat_entries_count_ = 0;  // the number of nat cache entries

  using NatTreeTraits = fbl::DefaultKeyedObjectTraits<nid_t, NatEntry>;
  using NatTree = fbl::WAVLTree<nid_t, std::unique_ptr<NatEntry>, NatTreeTraits>;
  using NatList = fbl::DoublyLinkedList<NatEntry *>;

  NatTree nat_cache_ __TA_GUARDED(nat_tree_lock_);       // cached nat entries
  NatList clean_nat_list_ __TA_GUARDED(nat_tree_lock_);  // a list for cached clean nats
  NatList dirty_nat_list_ __TA_GUARDED(nat_tree_lock_);  // a list for cached dirty nats

  std::mutex free_nid_list_lock_;                                // protect free nid list
  list_node_t free_nid_list_ __TA_GUARDED(free_nid_list_lock_);  // a list for free nids
  std::mutex build_lock_;                                        // lock for building free nids

  std::unique_ptr<uint8_t[]> nat_bitmap_ = nullptr;       // NAT bitmap pointer
  std::unique_ptr<uint8_t[]> nat_prev_bitmap_ = nullptr;  // NAT previous checkpoint bitmap pointer
  int nat_bitmap_size_ = 0;                               // NAT bitmap size
};

}  // namespace f2fs

#endif  // SRC_STORAGE_F2FS_NODE_H_