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_

#include <fbl/intrusive_double_list.h>
#include <fbl/intrusive_wavl_tree.h>

#include "src/storage/f2fs/bitmap.h"
#include "src/storage/f2fs/f2fs_internal.h"
#include "src/storage/f2fs/f2fs_layout.h"
#include "src/storage/f2fs/node_page.h"

class F2fs;

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
};

constexpr size_t kMaxNodeDepth = 4;
struct NodePath {
  nid_t ino = 0;
  block_t num_new_nodes = 0;
  size_t depth = 0;
  size_t node_offset[kMaxNodeDepth] = {
      0,
  };
  size_t offset_in_node[kMaxNodeDepth] = {
      0,
  };
};

bool IsSameDnode(NodePath &path, uint32_t node_offset);
zx::result<NodePath> GetNodePath(VnodeF2fs &vnode, pgoff_t block);
size_t GetOfsInDnode(NodePath &path);

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=(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() const { return ni_.blk_addr; }
  void SetBlockAddress(const block_t value) { ni_.blk_addr = value; }
  uint32_t GetIno() const { return ni_.ino; }
  void SetIno(const nid_t value) { ni_.ino = value; }
  uint8_t GetVersion() const { 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
};

class F2fsFakeDevTestFixture;

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

  explicit NodeManager(F2fs *fs);
  ~NodeManager();

  zx_status_t BuildNodeManager();
  zx_status_t GetNodePage(nid_t nid, LockedPage *out);

  // If it fails to find a node at |path|, it creates and returns a new node.
  zx::result<LockedPage> GetLockedDnodePage(NodePath &path, bool is_dir);
  // It returns a node page if it succeeds to find one at |path|.
  zx::result<LockedPage> FindLockedDnodePage(NodePath &path);

  void GetNodeInfo(nid_t nid, NodeInfo &out);
  void SetNodeAddr(NodeInfo &ni, block_t new_blkaddr);

  pgoff_t FsyncNodePages(nid_t ino) __TA_REQUIRES_SHARED(f2fs::GetGlobalLock());

  bool IsCheckpointedNode(nid_t nid);

  bool FlushNatsInJournal();
  zx_status_t FlushNatEntries();

  zx_status_t RecoverInodePage(NodePage &page);

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

  zx::result<nid_t> AllocNid() __TA_EXCLUDES(free_nid_tree_lock_);
  zx::result<nid_t> GetNextFreeNid() __TA_EXCLUDES(free_nid_tree_lock_);
  int AddFreeNid(nid_t nid) __TA_EXCLUDES(free_nid_tree_lock_);

  void TruncateNode(nid_t nid);
  zx::result<LockedPage> NewNodePage(nid_t ino, nid_t nid, bool is_dirt, size_t ofs);

  // for fsck and tests
  explicit 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() const { return nat_blkaddr_; }
  void SetNextScanNid(const nid_t value) __TA_EXCLUDES(build_lock_) {
    std::lock_guard lock(build_lock_);
    next_scan_nid_ = value;
  }
  nid_t GetNextScanNid() __TA_EXCLUDES(build_lock_) {
    std::lock_guard lock(build_lock_);
    return next_scan_nid_;
  }
  nid_t GetNatCount() const { return nat_entries_count_; }
  zx_status_t AllocNatBitmap(const uint32_t size) {
    nat_bitmap_size_ = size;
    nat_bitmap_.Reset(GetBitSize(nat_bitmap_size_));
    return ZX_OK;
  }
  void SetNatBitmap(const uint8_t *bitmap) {
    CloneBits(nat_bitmap_, bitmap, 0, GetBitSize(nat_bitmap_size_));
  }
  RawBitmap &GetNatBitmap() { return nat_bitmap_; }
  void GetNatBitmap(void *out);
  size_t GetFreeNidCount() __TA_EXCLUDES(free_nid_tree_lock_) {
    fs::SharedLock free_nid_lock(free_nid_tree_lock_);
    return free_nid_tree_.size();
  }

 private:
  void NodeInfoFromRawNat(NodeInfo &ni, RawNatEntry &raw_ne);
  // If the node page at |start| doesn't hit in the cache, do readahead node pages
  // from |start| in |parent|.
  zx::result<LockedPage> GetNextNodePage(LockedPage &parent, size_t start);
  friend class MapTester;
  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);
  zx::result<LockedPage> GetNextNatPage(nid_t nid);
  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 **out) __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 &raw_entry);
  int TryToFreeNats(int nr_shrink);

  void BuildFreeNids() __TA_EXCLUDES(free_nid_tree_lock_) __TA_EXCLUDES(build_lock_);
  zx::result<> LookupFreeNidList(nid_t n) __TA_REQUIRES(free_nid_tree_lock_);
  void RemoveFreeNid(nid_t nid) __TA_EXCLUDES(free_nid_tree_lock_);
  void RemoveFreeNidUnsafe(nid_t nid) __TA_REQUIRES(free_nid_tree_lock_);

  int ScanNatPage(Page &nat_page, nid_t start_nid);

  zx_status_t InitNodeManager();

  F2fs *const fs_ = nullptr;
  SuperblockInfo &superblock_info_;
  block_t nat_blkaddr_ = 0;  // starting block address of NAT

  std::shared_mutex 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::shared_mutex free_nid_tree_lock_;               // protect free nid list
  std::mutex build_lock_;                              // lock for building free nids
  nid_t max_nid_ = 0;                                  // the maximum number of node ids
  nid_t next_scan_nid_ __TA_GUARDED(build_lock_) = 0;  // the next nid to be scanned
  std::set<nid_t> free_nid_tree_ __TA_GUARDED(free_nid_tree_lock_);  // tree for free nids

  RawBitmap nat_bitmap_;          // NAT bitmap pointer
  RawBitmap nat_prev_bitmap_;     // NAT previous checkpoint bitmap pointer
  uint32_t nat_bitmap_size_ = 0;  // NAT bitmap size
};

}  // namespace f2fs

#endif  // SRC_STORAGE_F2FS_NODE_H_