// Copyright 2016 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.

#include <lib/cksum.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <map>
#include <memory>
#include <optional>
#include <utility>

#include <fs/journal/format.h>
#include <minfs/format.h>
#include <minfs/fsck.h>
#ifdef __Fuchsia__
#include <storage/buffer/owned_vmoid.h>
#else
#include <storage/buffer/array_buffer.h>
#endif

#include "lib/fit/string_view.h"
#include "minfs_private.h"

namespace minfs {

namespace {

#ifdef __Fuchsia__
using RawBitmap = bitmap::RawBitmapGeneric<bitmap::VmoStorage>;
#else
using RawBitmap = bitmap::RawBitmapGeneric<bitmap::DefaultStorage>;
#endif

enum class BlockType { DirectBlock = 0, IndirectBlock, DoubleIndirectBlock };

struct BlockInfo {
  ino_t owner;     // Inode number that maps this block.
  blk_t offset;    // Offset, in blocks, where this block is.
  BlockType type;  // What is this block used as.
};

const std::string kBlockInfoDirectStr("direct");
const std::string kBlockInfoIndirectStr("indirect");
const std::string kBlockInfoDoubleIndirectStr("double indirect");

// Given a type of block, returns human readable c-string for the block type.
std::string BlockTypeToString(BlockType type) {
  switch (type) {
    case BlockType::DirectBlock:
      return kBlockInfoDirectStr;
    case BlockType::IndirectBlock:
      return kBlockInfoIndirectStr;
    case BlockType::DoubleIndirectBlock:
      return kBlockInfoDoubleIndirectStr;
    default:
      ZX_ASSERT(false);
  }
}

// Returns the logical block accessed from the "indirect" structure within an inode.
// |direct| refers to the index within the indirect block.
blk_t LogicalBlockIndirect(blk_t indirect, blk_t direct = 0) {
  ZX_DEBUG_ASSERT(indirect < kMinfsIndirect);
  ZX_DEBUG_ASSERT(direct < kMinfsDirectPerIndirect);
  const blk_t start = kMinfsDirect;
  return start + (indirect * kMinfsDirectPerIndirect) + direct;
}
// Returns the logical block accessed from the "doubly indirect" structure within an inode.
// |indirect| refers to an index within the doubly_indirect block.
// |direct| refers to an index within |indirect|.
blk_t LogicalBlockDoublyIndirect(blk_t doubly_indirect, blk_t indirect = 0, blk_t direct = 0) {
  ZX_DEBUG_ASSERT(doubly_indirect < kMinfsDoublyIndirect);
  ZX_DEBUG_ASSERT(indirect < kMinfsDirectPerIndirect);
  ZX_DEBUG_ASSERT(direct < kMinfsDirectPerIndirect);
  const blk_t start = kMinfsDirect + (kMinfsIndirect * kMinfsDirectPerIndirect);
  return start + (kMinfsDirectPerDindirect * doubly_indirect) +
         (indirect * kMinfsDirectPerIndirect) + direct;
}

}  // namespace

class MinfsChecker {
 public:
  static zx_status_t Create(std::unique_ptr<Bcache> bc, const FsckOptions& options,
                            std::unique_ptr<MinfsChecker>* out);

  static std::unique_ptr<Bcache> Destroy(std::unique_ptr<MinfsChecker> checker) {
    return Minfs::Destroy(std::move(checker->fs_));
  }

  void CheckReserved();
  zx_status_t CheckInode(ino_t ino, ino_t parent, bool dot_or_dotdot);
  zx_status_t CheckUnlinkedInodes();
  zx_status_t CheckForUnusedBlocks() const;
  zx_status_t CheckForUnusedInodes() const;
  zx_status_t CheckLinkCounts() const;
  zx_status_t CheckAllocatedCounts() const;
  zx_status_t CheckSuperblockIntegrity() const;

  // "Set once"-style flag to identify if anything nonconforming
  // was found in the underlying filesystem -- even if it was fixed.
  bool conforming_;

 private:
  DISALLOW_COPY_ASSIGN_AND_MOVE(MinfsChecker);

  MinfsChecker();

  // Reads the inode and optionally checks the magic value to ensure it is either a file or
  // directory.
  zx_status_t GetInode(Inode* inode, ino_t ino, bool check_magic = true) const;

  // Returns the nth block within an inode, relative to the start of the
  // file. Returns the "next_n" which might contain a bno. This "next_n"
  // is for performance reasons -- it allows fsck to avoid repeatedly checking
  // the same indirect / doubly indirect blocks with all internal
  // bno unallocated.
  zx_status_t GetInodeNthBno(Inode* inode, blk_t n, blk_t* next_n, blk_t* bno_out);
  zx_status_t CheckDirectory(Inode* inode, ino_t ino, ino_t parent, uint32_t flags);
  std::optional<std::string> CheckDataBlock(blk_t bno, BlockInfo block_info);
  zx_status_t CheckFile(Inode* inode, ino_t ino);

  std::unique_ptr<Minfs> fs_;
  RawBitmap checked_inodes_;
  RawBitmap checked_blocks_;
  ino_t max_inode_ = 0;

  // blk_info_ provides reverse lookup capability - a block number is mapped to
  // a set of BlockInfo. The filesystem is inconsistent if a block has more than
  // one <inode, offset, type>.
  std::map<blk_t, std::vector<BlockInfo>> blk_info_;

  uint32_t alloc_inodes_;
  uint32_t alloc_blocks_;
  fbl::Array<int32_t> links_;

  blk_t cached_doubly_indirect_;
  blk_t cached_indirect_;
  uint8_t doubly_indirect_cache_[kMinfsBlockSize];
  uint8_t indirect_cache_[kMinfsBlockSize];
};

zx_status_t MinfsChecker::GetInode(Inode* inode, ino_t ino, bool check_magic) const {
  if (ino >= fs_->Info().inode_count) {
    FS_TRACE_ERROR("check: ino %u out of range (>=%u)\n", ino, fs_->Info().inode_count);
    return ZX_ERR_OUT_OF_RANGE;
  }

  fs_->GetInodeManager()->Load(ino, inode);
  if (check_magic && (inode->magic != kMinfsMagicFile) && (inode->magic != kMinfsMagicDir)) {
    FS_TRACE_ERROR("check: ino %u has bad magic %#x\n", ino, inode->magic);
    return ZX_ERR_IO_DATA_INTEGRITY;
  }
  return ZX_OK;
}

#define CD_DUMP 1
#define CD_RECURSE 2

zx_status_t MinfsChecker::GetInodeNthBno(Inode* inode, blk_t n, blk_t* next_n, blk_t* bno_out) {
  // The default value for the "next n". It's easier to set it here anyway,
  // since we proceed to modify n in the code below.
  *next_n = n + 1;
  if (n < kMinfsDirect) {
    *bno_out = inode->dnum[n];
    return ZX_OK;
  }

  n -= kMinfsDirect;
  uint32_t i = n / kMinfsDirectPerIndirect;  // indirect index
  uint32_t j = n % kMinfsDirectPerIndirect;  // direct index

  if (i < kMinfsIndirect) {
    blk_t ibno;
    if ((ibno = inode->inum[i]) == 0) {
      *bno_out = 0;
      *next_n = kMinfsDirect + (i + 1) * kMinfsDirectPerIndirect;
      return ZX_OK;
    }

    if (cached_indirect_ != ibno) {
      zx_status_t status;
      if ((status = fs_->ReadDat(ibno, indirect_cache_)) != ZX_OK) {
        return status;
      }
      cached_indirect_ = ibno;
    }

    uint32_t* ientry = reinterpret_cast<uint32_t*>(indirect_cache_);
    *bno_out = ientry[j];
    return ZX_OK;
  }

  n -= kMinfsIndirect * kMinfsDirectPerIndirect;
  i = n / (kMinfsDirectPerDindirect);  // doubly indirect index
  n -= (i * kMinfsDirectPerDindirect);
  j = n / kMinfsDirectPerIndirect;           // indirect index
  uint32_t k = n % kMinfsDirectPerIndirect;  // direct index

  if (i < kMinfsDoublyIndirect) {
    blk_t dibno;
    if ((dibno = inode->dinum[i]) == 0) {
      *bno_out = 0;
      *next_n = kMinfsDirect + kMinfsIndirect * kMinfsDirectPerIndirect +
                (i + 1) * kMinfsDirectPerDindirect;
      return ZX_OK;
    }

    if (cached_doubly_indirect_ != dibno) {
      zx_status_t status;
      if ((status = fs_->ReadDat(dibno, doubly_indirect_cache_)) != ZX_OK) {
        return status;
      }
      cached_doubly_indirect_ = dibno;
    }

    uint32_t* dientry = reinterpret_cast<uint32_t*>(doubly_indirect_cache_);
    blk_t ibno;
    if ((ibno = dientry[j]) == 0) {
      *bno_out = 0;
      *next_n = kMinfsDirect + kMinfsIndirect * kMinfsDirectPerIndirect +
                (i * kMinfsDirectPerDindirect) + (j + 1) * kMinfsDirectPerIndirect;
      return ZX_OK;
    }

    if (cached_indirect_ != ibno) {
      zx_status_t status;
      if ((status = fs_->ReadDat(ibno, indirect_cache_)) != ZX_OK) {
        return status;
      }
      cached_indirect_ = ibno;
    }

    uint32_t* ientry = reinterpret_cast<uint32_t*>(indirect_cache_);
    *bno_out = ientry[k];
    return ZX_OK;
  }

  return ZX_ERR_OUT_OF_RANGE;
}

zx_status_t MinfsChecker::CheckDirectory(Inode* inode, ino_t ino, ino_t parent, uint32_t flags) {
  unsigned eno = 0;
  bool dot = false;
  bool dotdot = false;
  uint32_t dirent_count = 0;

  zx_status_t status;
  fbl::RefPtr<VnodeMinfs> vn;
  VnodeMinfs::Recreate(fs_.get(), ino, &vn);

  size_t off = 0;
  while (true) {
    uint32_t data[MINFS_DIRENT_SIZE];
    size_t actual;
    status = vn->ReadInternal(nullptr, data, MINFS_DIRENT_SIZE, off, &actual);
    if (status == ZX_OK && actual == 0 && inode->link_count == 0 && parent == 0) {
      // This is OK as it's an unlinked directory.
      break;
    }
    if (status != ZX_OK || actual != MINFS_DIRENT_SIZE) {
      FS_TRACE_ERROR("check: ino#%u: Could not read de[%u] at %zd\n", eno, ino, off);
      if (inode->dirent_count >= 2 && inode->dirent_count == eno - 1) {
        // So we couldn't read the last direntry, for whatever reason, but our
        // inode says that we shouldn't have been able to read it anyway.
        FS_TRACE_ERROR("check: de count (%u) > inode_dirent_count (%u)\n", eno,
                       inode->dirent_count);
      }
      return status != ZX_OK ? status : ZX_ERR_IO;
    }
    Dirent* de = reinterpret_cast<Dirent*>(data);
    uint32_t rlen = static_cast<uint32_t>(MinfsReclen(de, off));
    uint32_t dlen = DirentSize(de->namelen);
    bool is_last = de->reclen & kMinfsReclenLast;
    if (!is_last && ((rlen < MINFS_DIRENT_SIZE) || (dlen > rlen) || (dlen > kMinfsMaxDirentSize) ||
                     (rlen & 3))) {
      FS_TRACE_ERROR("check: ino#%u: de[%u]: bad dirent reclen (%u)\n", ino, eno, rlen);
      return ZX_ERR_IO_DATA_INTEGRITY;
    }
    if (de->ino == 0) {
      if (flags & CD_DUMP) {
        FS_TRACE_DEBUG("ino#%u: de[%u]: <empty> reclen=%u\n", ino, eno, rlen);
      }
    } else {
      // Re-read the dirent to acquire the full name
      uint32_t record_full[DirentSize(NAME_MAX)];
      status = vn->ReadInternal(nullptr, record_full, DirentSize(de->namelen), off, &actual);
      if (status != ZX_OK || actual != DirentSize(de->namelen)) {
        FS_TRACE_ERROR("check: Error reading dirent of size: %u\n", DirentSize(de->namelen));
        return ZX_ERR_IO;
      }
      de = reinterpret_cast<Dirent*>(record_full);
      bool dot_or_dotdot = false;

      if ((de->namelen == 0) || (de->namelen > (rlen - MINFS_DIRENT_SIZE))) {
        FS_TRACE_ERROR("check: ino#%u: de[%u]: invalid namelen %u\n", ino, eno, de->namelen);
        return ZX_ERR_IO_DATA_INTEGRITY;
      }
      if ((de->namelen == 1) && (de->name[0] == '.')) {
        if (dot) {
          FS_TRACE_ERROR("check: ino#%u: multiple '.' entries\n", ino);
          conforming_ = false;
        }
        dot_or_dotdot = true;
        dot = true;
        if (de->ino != ino) {
          FS_TRACE_ERROR("check: ino#%u: de[%u]: '.' ino=%u (not self!)\n", ino, eno, de->ino);
          conforming_ = false;
        }
      }
      if ((de->namelen == 2) && (de->name[0] == '.') && (de->name[1] == '.')) {
        if (dotdot) {
          FS_TRACE_ERROR("check: ino#%u: multiple '..' entries\n", ino);
          conforming_ = false;
        }
        dot_or_dotdot = true;
        dotdot = true;
        if (de->ino != parent) {
          FS_TRACE_ERROR("check: ino#%u: de[%u]: '..' ino=%u (not parent (ino#%u)!)\n", ino, eno,
                         de->ino, parent);
          conforming_ = false;
        }
      }
      if (flags & CD_DUMP) {
        FS_TRACE_DEBUG("ino#%u: de[%u]: ino=%u type=%u '%.*s' %s\n", ino, eno, de->ino, de->type,
                       de->namelen, de->name, is_last ? "[last]" : "");
      }

      if (flags & CD_RECURSE) {
        if ((status = CheckInode(de->ino, ino, dot_or_dotdot)) < 0) {
          return status;
        }
      }
      dirent_count++;
    }
    if (is_last) {
      break;
    } else {
      off += rlen;
    }
    eno++;
  }
  if (inode->link_count == 0 && inode->dirent_count != 0) {
    FS_TRACE_ERROR("check: dirent_count (%u) for unlinked directory != 0\n", inode->dirent_count);
    conforming_ = false;
  }
  if (dirent_count != inode->dirent_count) {
    FS_TRACE_ERROR("check: ino#%u: dirent_count of %u != %u (actual)\n", ino, inode->dirent_count,
                   dirent_count);
    conforming_ = false;
  }
  if (dot == false && inode->link_count > 0) {
    FS_TRACE_ERROR("check: ino#%u: directory missing '.'\n", ino);
    conforming_ = false;
  }
  if (dotdot == false && inode->link_count > 0) {
    FS_TRACE_ERROR("check: ino#%u: directory missing '..'\n", ino);
    conforming_ = false;
  }
  return ZX_OK;
}

std::optional<std::string> MinfsChecker::CheckDataBlock(blk_t bno, BlockInfo block_info) {
  if (bno == 0) {
    return std::string("reserved bno");
  }
  if (bno >= fs_->Info().block_count) {
    return std::string("out of range");
  }
  if (!fs_->GetBlockAllocator().CheckAllocated(bno)) {
    return std::string("not allocated");
  }
  if (checked_blocks_.Get(bno, bno + 1)) {
    auto entries = blk_info_[bno].size();
    // The entries are printed as
    // "double-allocated"
    // "  <ino: 4294967295, off: 4294967295 type: DI>\n"
    std::string str("double-allocated\n");
    for (size_t i = 0; i < entries; i++) {
      str.append("  <ino: " + std::to_string(blk_info_[bno][i].owner) +
                 ", off: " + std::to_string(blk_info_[bno][i].offset) +
                 " type: " + BlockTypeToString(blk_info_[bno][i].type) + ">\n");
    }
    blk_info_[bno].push_back(block_info);
    return str;
  }
  checked_blocks_.Set(bno, bno + 1);
  std::vector<BlockInfo> vec;
  vec.push_back(block_info);
  blk_info_.insert(std::pair<blk_t, std::vector<BlockInfo>>(bno, vec));
  alloc_blocks_++;
  return std::nullopt;
}

zx_status_t MinfsChecker::CheckFile(Inode* inode, ino_t ino) {
  FS_TRACE_DEBUG("Direct blocks: \n");
  for (unsigned n = 0; n < kMinfsDirect; n++) {
    FS_TRACE_DEBUG(" %d,", inode->dnum[n]);
  }
  FS_TRACE_DEBUG(" ...\n");

  uint32_t block_count = 0;

  // count and sanity-check indirect blocks
  for (unsigned n = 0; n < kMinfsIndirect; n++) {
    if (inode->inum[n]) {
      BlockInfo block_info = {ino, LogicalBlockIndirect(n), BlockType::IndirectBlock};
      auto msg = CheckDataBlock(inode->inum[n], block_info);
      if (msg) {
        FS_TRACE_WARN("check: ino#%u: indirect block %u(@%u): %s\n", ino, n, inode->inum[n],
                      msg.value().c_str());
        conforming_ = false;
      }
      block_count++;
    }
  }

  // count and sanity-check doubly indirect blocks
  for (unsigned n = 0; n < kMinfsDoublyIndirect; n++) {
    if (inode->dinum[n]) {
      BlockInfo block_info = {ino, LogicalBlockDoublyIndirect(n), BlockType::DoubleIndirectBlock};
      auto msg = CheckDataBlock(inode->dinum[n], block_info);
      if (msg) {
        FS_TRACE_WARN("check: ino#%u: doubly indirect block %u(@%u): %s\n", ino, n, inode->dinum[n],
                      msg.value().c_str());
        conforming_ = false;
      }
      block_count++;

      char data[kMinfsBlockSize];
      zx_status_t status;
      if ((status = fs_->ReadDat(inode->dinum[n], data)) != ZX_OK) {
        return status;
      }
      uint32_t* entry = reinterpret_cast<uint32_t*>(data);

      for (unsigned m = 0; m < kMinfsDirectPerIndirect; m++) {
        if (entry[m]) {
          BlockInfo block_info = {ino, LogicalBlockDoublyIndirect(n, m), BlockType::IndirectBlock};
          msg = CheckDataBlock(entry[m], block_info);
          if (msg) {
            FS_TRACE_WARN("check: ino#%u: indirect block (in dind) %u(@%u): %s\n", ino, m, entry[m],
                          msg.value().c_str());
            conforming_ = false;
          }
          block_count++;
        }
      }
    }
  }

  // count and sanity-check data blocks

  // The next block which would be allocated if we expand the file size
  // by a single block.
  unsigned next_blk = 0;
  cached_doubly_indirect_ = 0;
  cached_indirect_ = 0;

  blk_t n = 0;
  while (true) {
    zx_status_t status;
    blk_t bno;
    blk_t next_n;
    if ((status = GetInodeNthBno(inode, n, &next_n, &bno)) < 0) {
      if (status == ZX_ERR_OUT_OF_RANGE) {
        break;
      } else {
        return status;
      }
    }
    assert(next_n > n);
    if (bno) {
      next_blk = n + 1;
      block_count++;
      BlockInfo block_info = {ino, n, BlockType::DirectBlock};
      auto msg = CheckDataBlock(bno, block_info);
      if (msg) {
        FS_TRACE_WARN("check: ino#%u: block %u(@%u): %s\n", ino, n, bno, msg.value().c_str());
        conforming_ = false;
      }
    }
    n = next_n;
  }
  if (next_blk) {
    unsigned max_blocks = fbl::round_up(inode->size, kMinfsBlockSize) / kMinfsBlockSize;
    if (next_blk > max_blocks) {
      FS_TRACE_WARN("check: ino#%u: filesize too small\n", ino);
      conforming_ = false;
    }
  }
  if (block_count != inode->block_count) {
    FS_TRACE_WARN("check: ino#%u: block count %u, actual blocks %u\n", ino, inode->block_count,
                  block_count);
    conforming_ = false;
  }
  return ZX_OK;
}

void MinfsChecker::CheckReserved() {
  // Check reserved inode '0'.
  if (fs_->GetInodeManager()->GetInodeAllocator()->CheckAllocated(0)) {
    ZX_ASSERT(!checked_inodes_.Get(0, 1));
    checked_inodes_.Set(0, 1);
    alloc_inodes_++;
  } else {
    FS_TRACE_WARN("check: reserved inode#0: not marked in-use\n");
    conforming_ = false;
  }

  // Check reserved data block '0'.
  if (fs_->GetBlockAllocator().CheckAllocated(0)) {
    checked_blocks_.Set(0, 1);
    alloc_blocks_++;
  } else {
    FS_TRACE_WARN("check: reserved block#0: not marked in-use\n");
    conforming_ = false;
  }
}

zx_status_t MinfsChecker::CheckInode(ino_t ino, ino_t parent, bool dot_or_dotdot) {
  Inode inode;
  zx_status_t status;

  if ((status = GetInode(&inode, ino)) < 0) {
    FS_TRACE_ERROR("check: ino#%u: not readable: %d\n", ino, status);
    return status;
  }

  bool prev_checked = checked_inodes_.Get(ino, ino + 1);

  if (inode.magic == kMinfsMagicDir && prev_checked && !dot_or_dotdot) {
    FS_TRACE_ERROR(
        "check: ino#%u: Multiple hard links to directory (excluding '.' and '..') found\n", ino);
    return ZX_ERR_BAD_STATE;
  }

  links_[ino - 1] += 1;

  if (prev_checked) {
    // we've been here before
    return ZX_OK;
  }

  links_[ino - 1] -= inode.link_count;
  checked_inodes_.Set(ino, ino + 1);
  max_inode_ = std::max(ino, max_inode_);
  alloc_inodes_++;

  if (!fs_->GetInodeManager()->GetInodeAllocator()->CheckAllocated(ino)) {
    FS_TRACE_WARN("check: ino#%u: not marked in-use\n", ino);
    conforming_ = false;
  }

  if (inode.magic == kMinfsMagicDir) {
    FS_TRACE_DEBUG("ino#%u: DIR blks=%u links=%u\n", ino, inode.block_count, inode.link_count);
    if ((status = CheckFile(&inode, ino)) < 0) {
      return status;
    }
    if ((status = CheckDirectory(&inode, ino, parent, CD_DUMP)) < 0) {
      return status;
    }
    if ((status = CheckDirectory(&inode, ino, parent, CD_RECURSE)) < 0) {
      return status;
    }
  } else {
    if (ino == kMinfsRootIno) {
      FS_TRACE_ERROR("Root inode must be a directory\n");
      return ZX_ERR_BAD_STATE;
    }
    FS_TRACE_DEBUG("ino#%u: FILE blks=%u links=%u size=%u\n", ino, inode.block_count,
                   inode.link_count, inode.size);
    if ((status = CheckFile(&inode, ino)) < 0) {
      return status;
    }
  }
  return ZX_OK;
}

zx_status_t MinfsChecker::CheckUnlinkedInodes() {
  ino_t last_ino = 0;
  ino_t next_ino = fs_->Info().unlinked_head;
  ino_t unlinked_count = 0;

  while (next_ino != 0) {
    unlinked_count++;

    Inode inode;
    zx_status_t status = GetInode(&inode, next_ino);
    if (status != ZX_OK) {
      FS_TRACE_ERROR("check: ino#%u: not readable: %d\n", next_ino, status);
      return status;
    }

    if (inode.link_count > 0) {
      FS_TRACE_ERROR("check: ino#%u: should have 0 links\n", next_ino);
      return ZX_ERR_BAD_STATE;
    }

    if (inode.last_inode != last_ino) {
      FS_TRACE_ERROR("check: ino#%u: incorrect last unlinked inode\n", next_ino);
      return ZX_ERR_BAD_STATE;
    }

    links_[next_ino - 1] = -1;

    if ((status = CheckInode(next_ino, 0, 0)) != ZX_OK) {
      FS_TRACE_ERROR("minfs_check: CheckInode failure: %d\n", status);
      return status;
    }

    last_ino = next_ino;
    next_ino = inode.next_inode;
  }

  if (fs_->Info().unlinked_tail != last_ino) {
    FS_TRACE_ERROR("minfs_check: Incorrect unlinked tail: %d\n", fs_->Info().unlinked_tail);
    return ZX_ERR_BAD_STATE;
  }

  if (unlinked_count > 0) {
    FS_TRACE_WARN("minfs_check: Warning: %u unlinked inodes found\n", unlinked_count);
  }

  return ZX_OK;
}

zx_status_t MinfsChecker::CheckForUnusedBlocks() const {
  unsigned missing = 0;

  for (unsigned n = 0; n < fs_->Info().block_count; n++) {
    if (fs_->GetBlockAllocator().CheckAllocated(n)) {
      if (!checked_blocks_.Get(n, n + 1)) {
        missing++;
      }
    }
  }
  if (missing) {
    FS_TRACE_ERROR("check: %u allocated block%s not in use\n", missing, missing > 1 ? "s" : "");
    return ZX_ERR_BAD_STATE;
  }
  return ZX_OK;
}

zx_status_t MinfsChecker::CheckForUnusedInodes() const {
  unsigned missing = 0, bad_magic = 0;
  Inode inode;
  // It can slow things down considerably to read and check every unused inode, so only check 1 to 2
  // blocks worth beyond the maximum.
  const size_t check_magic_up_to =
      fbl::round_up(max_inode_ + kMinfsInodesPerBlock, kMinfsInodesPerBlock);
  for (unsigned n = 0; n < fs_->Info().inode_count; n++) {
    if (fs_->GetInodeManager()->GetInodeAllocator()->CheckAllocated(n)) {
      if (!checked_inodes_.Get(n, n + 1)) {
        missing++;
      }
    } else if (n < check_magic_up_to) {
      zx_status_t status = GetInode(&inode, n, /*check_magic=*/false);
      if (status != ZX_OK) {
        FS_TRACE_ERROR("check: ino#%u: not readable: %d\n", n, status);
        return status;
      }
      // Format creates inodes with magic == 0.
      if (inode.magic != kMinfsMagicPurged && inode.magic != 0) {
        bad_magic++;
      }
    }
  }
  // Minfs behaviour was changed in revision 1 so that purged inodes have their magic field changed
  // to kMinfsMagicPurged. Prior to this, the inodes were left intact.
  if (missing > 0 || (bad_magic > 0 && fs_->Info().oldest_revision >= 1)) {
    if (bad_magic > 0) {
      FS_TRACE_ERROR("check: %u free inode%s with bad magic values\n", bad_magic,
                     bad_magic > 1 ? "s" : "");
    }
    if (missing > 0) {
      FS_TRACE_ERROR("check: %u allocated inode%s not in use\n", missing, missing > 1 ? "s" : "");
    }
    return ZX_ERR_BAD_STATE;
  }
  if (bad_magic > 0) {
    FS_TRACE_WARN("check: %u free inode%s with bad magic values\n", bad_magic,
                  bad_magic > 1 ? "s" : "");
  }
  return ZX_OK;
}

zx_status_t MinfsChecker::CheckLinkCounts() const {
  unsigned error = 0;
  for (uint32_t n = 0; n < fs_->Info().inode_count; n++) {
    if (links_[n] != 0) {
      error += 1;
      FS_TRACE_ERROR("check: inode#%u has incorrect link count %u\n", n + 1, links_[n]);
      return ZX_ERR_BAD_STATE;
    }
  }
  if (error) {
    FS_TRACE_ERROR("check: %u inode%s with incorrect link count\n", error, error > 1 ? "s" : "");
    return ZX_ERR_BAD_STATE;
  }
  return ZX_OK;
}

zx_status_t MinfsChecker::CheckAllocatedCounts() const {
  zx_status_t status = ZX_OK;
  if (alloc_blocks_ != fs_->Info().alloc_block_count) {
    FS_TRACE_ERROR("check: incorrect allocated block count %u (should be %u)\n",
                   fs_->Info().alloc_block_count, alloc_blocks_);
    status = ZX_ERR_BAD_STATE;
  }

  if (alloc_inodes_ != fs_->Info().alloc_inode_count) {
    FS_TRACE_ERROR("check: incorrect allocated inode count %u (should be %u)\n",
                   fs_->Info().alloc_inode_count, alloc_inodes_);
    status = ZX_ERR_BAD_STATE;
  }

  return status;
}

zx_status_t MinfsChecker::CheckSuperblockIntegrity() const {
  char data[kMinfsBlockSize];
  blk_t journal_block;

#ifdef __Fuchsia__
  journal_block = static_cast<blk_t>(JournalStartBlock(fs_->Info()));
#else
  journal_block = fs_->GetBlockOffsets().JournalStartBlock();
#endif

  if (fs_->bc_->Readblk(journal_block, data) < 0) {
    FS_TRACE_ERROR("minfs: could not read journal block\n");
    return ZX_ERR_IO;
  }

  // Check that the journal superblock is valid.
  fs::JournalInfo* journal_info = reinterpret_cast<fs::JournalInfo*>(data);
  if (journal_info->magic != fs::kJournalMagic) {
    FS_TRACE_ERROR("minfs: invalid journal magic\n");
    return ZX_ERR_BAD_STATE;
  }

  uint32_t old_checksum = journal_info->checksum;
  journal_info->checksum = 0;
  journal_info->checksum = crc32(0, reinterpret_cast<uint8_t*>(data), sizeof(fs::JournalInfo));
  if (journal_info->checksum != old_checksum) {
    FS_TRACE_ERROR("minfs: invalid journal checksum\n");
    return ZX_ERR_BAD_STATE;
  }

  // Check that the backup superblock is valid.
  blk_t backup_location;
  if ((fs_->Info().flags & kMinfsFlagFVM) == 0) {
    backup_location = kNonFvmSuperblockBackup;
  } else {
#ifdef __Fuchsia__
    backup_location = kFvmSuperblockBackup;
#else
    backup_location = fs_->GetBlockOffsets().IntegrityStartBlock();
#endif
  }

  if (fs_->bc_->Readblk(backup_location, data) < 0) {
    FS_TRACE_ERROR("minfs: could not read backup superblock\n");
    return ZX_ERR_IO;
  }

  Superblock* backup_info = reinterpret_cast<Superblock*>(data);
#ifdef __Fuchsia__
  return CheckSuperblock(backup_info, fs_->bc_->device(), fs_->bc_->Maxblk());
#else
  return CheckSuperblock(backup_info, fs_->bc_->Maxblk());
#endif
}

MinfsChecker::MinfsChecker()
    : conforming_(true), fs_(nullptr), alloc_inodes_(0), alloc_blocks_(0), links_() {}

zx_status_t MinfsChecker::Create(std::unique_ptr<Bcache> bc, const FsckOptions& fsck_options,
                                 std::unique_ptr<MinfsChecker>* out) {
  MountOptions options = {};
  if (fsck_options.repair) {
    options.readonly_after_initialization = false;
    options.repair_filesystem = true;
    options.use_journal = true;
  } else {
    options.readonly_after_initialization = false;
    options.repair_filesystem = false;
    options.use_journal = false;
  }
  options.fsck_after_every_transaction = false;
  options.readonly = fsck_options.read_only;
  std::unique_ptr<Minfs> fs;
  zx_status_t status = Minfs::Create(std::move(bc), options, &fs);
  if (status != ZX_OK) {
    FS_TRACE_ERROR("MinfsChecker::Create Failed to Create Minfs: %d\n", status);
    return status;
  }

  const Superblock& info = fs->Info();

  auto checker = std::unique_ptr<MinfsChecker>(new MinfsChecker());
  checker->links_.reset(new int32_t[info.inode_count]{0}, info.inode_count);
  checker->links_[0] = -1;
  checker->cached_doubly_indirect_ = 0;
  checker->cached_indirect_ = 0;

  if ((status = checker->checked_inodes_.Reset(info.inode_count)) != ZX_OK) {
    FS_TRACE_ERROR("MinfsChecker::Init Failed to reset checked inodes: %d\n", status);
    return status;
  }
  if ((status = checker->checked_blocks_.Reset(info.block_count)) != ZX_OK) {
    FS_TRACE_ERROR("MinfsChecker::Init Failed to reset checked blocks: %d\n", status);
    return status;
  }
  checker->fs_ = std::move(fs);
  *out = std::move(checker);
  return ZX_OK;
}

// Write Superblock and Backup Superblock to disk.
#ifdef __Fuchsia__
zx_status_t WriteSuperBlockAndBackupSuperblock(fs::DeviceTransactionHandler* transaction_handler,
                                               block_client::BlockDevice* device,
                                               Superblock* info) {
#else
zx_status_t WriteSuperBlockAndBackupSuperblock(fs::TransactionHandler* transaction_handler,
                                               Superblock* info) {
#endif
#ifdef __Fuchsia__
  storage::VmoBuffer buffer;
  zx_status_t status =
      buffer.Initialize(transaction_handler->GetDevice(), 1, kMinfsBlockSize, "fsck-super-block");
  if (status != ZX_OK) {
    return status;
  }
#else
  storage::ArrayBuffer buffer(1, kMinfsBlockSize);
#endif
  memcpy(buffer.Data(0), info, sizeof(*info));
  fs::BufferedOperationsBuilder builder;
  builder
      .Add(storage::Operation{.type = storage::OperationType::kWrite,
                              .vmo_offset = 0,
                              .dev_offset = kSuperblockStart,
                              .length = 1},
           &buffer)
      .Add(storage::Operation{.type = storage::OperationType::kWrite,
                              .vmo_offset = 0,
                              .dev_offset = (info->flags & kMinfsFlagFVM ? kFvmSuperblockBackup
                                                                         : kNonFvmSuperblockBackup),
                              .length = 1},
           &buffer);
  return transaction_handler->RunRequests(builder.TakeOperations());
}

// Reads backup superblock from correct location depending on whether filesystem has FVM support.
#ifdef __Fuchsia__
zx_status_t ReadBackupSuperblock(fs::TransactionHandler* transaction_handler,
                                 block_client::BlockDevice* device, uint32_t max_blocks,
                                 uint32_t backup_location, Superblock* out_backup) {
  zx_status_t status = device->ReadBlock(backup_location, kMinfsBlockSize, out_backup);
  if (status != ZX_OK) {
    return status;
  }
  status = CheckSuperblock(out_backup, device, max_blocks);
  if (status != ZX_OK) {
    return status;
  }
  // Found a valid backup superblock. Confirm if the FVM flags are set in the backup superblock.
  if ((backup_location == kFvmSuperblockBackup) && ((out_backup->flags & kMinfsFlagFVM) == 0)) {
    return ZX_ERR_BAD_STATE;
  } else if ((backup_location == kNonFvmSuperblockBackup) &&
             ((out_backup->flags & kMinfsFlagFVM) != 0)) {
    return ZX_ERR_BAD_STATE;
  }

  return ZX_OK;
}
#endif

// Repairs superblock from backup.
#ifdef __Fuchsia__
zx_status_t RepairSuperblock(fs::DeviceTransactionHandler* transaction_handler,
                             block_client::BlockDevice* device, uint32_t max_blocks,
                             Superblock* info_out) {
  Superblock backup_info;
  // Try the FVM backup location first.
  zx_status_t status = ReadBackupSuperblock(transaction_handler, device, max_blocks,
                                            kFvmSuperblockBackup, &backup_info);

  if (status != ZX_OK) {
    // Try the non-fvm backup superblock location.
    status = ReadBackupSuperblock(transaction_handler, device, max_blocks, kNonFvmSuperblockBackup,
                                  &backup_info);
  }

  if (status != ZX_OK) {
    FS_TRACE_ERROR("Fsck::RepairSuperblock failed. Unrepairable superblock: %d\n", status);
    return status;
  }
  FS_TRACE_INFO("Superblock corrupted. Repairing filesystem from backup superblock.\n");

  // Try to reconstruct alloc_*_counts of the backup superblock, since the
  // alloc_*_counts might be out-of-sync with the actual values.
  status = ReconstructAllocCounts(transaction_handler, device, &backup_info);

  if (status != ZX_OK) {
    FS_TRACE_ERROR("Fsck::ReconstructAllocCounts failed. Unrepairable superblock: %d\n", status);
    return status;
  }
  // Recalculate checksum.
  UpdateChecksum(&backup_info);

  // Update superblock and backup superblock.
  status = WriteSuperBlockAndBackupSuperblock(transaction_handler, device, &backup_info);

  if (status != ZX_OK) {
    FS_TRACE_ERROR("Fsck::RepairSuperblock failed to repair superblock from backup :%d", status);
  }

  // Updating in-memory info.
  memcpy(info_out, &backup_info, sizeof(backup_info));
  return status;
}
#endif

zx_status_t LoadSuperblock(Bcache* bc, Superblock* out_info) {
  zx_status_t status = bc->Readblk(kSuperblockStart, out_info);
  if (status != ZX_OK) {
    FS_TRACE_ERROR("minfs: could not read info block.\n");
    return status;
  }
  DumpInfo(out_info);
#ifdef __Fuchsia__
  status = CheckSuperblock(out_info, bc->device(), bc->Maxblk());
#else
  status = CheckSuperblock(out_info, bc->Maxblk());
#endif
  if (status != ZX_OK) {
    FS_TRACE_ERROR("Fsck: check_info failure: %d\n", status);
    return status;
  }
  return ZX_OK;
}

zx_status_t UsedDataSize(std::unique_ptr<Bcache>& bc, uint64_t* out_size) {
  zx_status_t status;
  Superblock info = {};
  if ((status = LoadSuperblock(bc.get(), &info)) != ZX_OK) {
    return status;
  }

  *out_size = (info.alloc_block_count * info.block_size);
  return ZX_OK;
}

zx_status_t UsedInodes(std::unique_ptr<Bcache>& bc, uint64_t* out_inodes) {
  zx_status_t status;
  Superblock info = {};
  if ((status = LoadSuperblock(bc.get(), &info)) != ZX_OK) {
    return status;
  }

  *out_inodes = info.alloc_inode_count;
  return ZX_OK;
}

zx_status_t UsedSize(std::unique_ptr<Bcache>& bc, uint64_t* out_size) {
  zx_status_t status;
  Superblock info = {};
  if ((status = LoadSuperblock(bc.get(), &info)) != ZX_OK) {
    return status;
  }

  *out_size = (NonDataBlocks(info) + info.alloc_block_count) * info.block_size;
  return ZX_OK;
}

#ifdef __Fuchsia__
zx_status_t CalculateBitsSetBitmap(fs::TransactionHandler* transaction_handler,
                                   block_client::BlockDevice* device, blk_t start_block,
                                   uint32_t num_blocks, uint32_t* out_bits_set) {
#else
zx_status_t CalculateBitsSetBitmap(fs::TransactionHandler* transaction_handler, blk_t start_block,
                                   uint32_t num_blocks, uint32_t* out_bits_set) {
#endif
  minfs::RawBitmap bitmap;
  zx_status_t status = bitmap.Reset(num_blocks * kMinfsBlockBits);
  if (status != ZX_OK) {
    return status;
  }

#ifdef __Fuchsia__
  storage::OwnedVmoid map_vmoid;
  status =
      device->BlockAttachVmo(bitmap.StorageUnsafe()->GetVmo(), &map_vmoid.GetReference(device));
  if (status != ZX_OK) {
    return status;
  }
  fs::internal::BorrowedBuffer buffer(map_vmoid.get());
#else
  fs::internal::BorrowedBuffer buffer(bitmap.StorageUnsafe()->GetData());
#endif
  status =
      transaction_handler->RunOperation(storage::Operation{.type = storage::OperationType::kRead,
                                                           .vmo_offset = 0,
                                                           .dev_offset = start_block,
                                                           .length = num_blocks},
                                        &buffer);
  if (status != ZX_OK) {
    return status;
  }

  // Efficiently iterate through the bitmap to count the number of bits set in the bitmap.
  size_t off = 0;
  size_t bitmap_size = bitmap.size();
  size_t count = 0;

  while (off < bitmap_size) {
    size_t ind = 0;
    if (bitmap.Find(true, off, bitmap_size, 1, &ind) == ZX_OK) {
      size_t scan_ind = 0;
      if (bitmap.Scan(ind, bitmap_size, true, &scan_ind)) {
        count += (bitmap_size - ind);
        break;
      }
      count += (scan_ind - ind);
      off = scan_ind + 1;

    } else {
      break;
    }
  }

  *out_bits_set = static_cast<uint32_t>(count);
  return ZX_OK;
}

#ifdef __Fuchsia__
zx_status_t ReconstructAllocCounts(fs::TransactionHandler* transaction_handler,
                                   block_client::BlockDevice* device, Superblock* out_info) {
#else
zx_status_t ReconstructAllocCounts(fs::TransactionHandler* transaction_handler,
                                   Superblock* out_info) {
#endif
  uint32_t allocation_bitmap_num_blocks =
      (out_info->block_count + kMinfsBlockBits - 1) / kMinfsBlockBits;

#ifdef __Fuchsia__
  // Correct allocated block count.
  zx_status_t status =
      CalculateBitsSetBitmap(transaction_handler, device, out_info->abm_block,
                             allocation_bitmap_num_blocks, &(out_info->alloc_block_count));
#else
  zx_status_t status =
      CalculateBitsSetBitmap(transaction_handler, out_info->abm_block, allocation_bitmap_num_blocks,
                             &(out_info->alloc_block_count));
#endif
  if (status != ZX_OK) {
    return status;
  }
  uint32_t inode_bitmap_num_blocks =
      (out_info->inode_count + kMinfsBlockBits - 1) / kMinfsBlockBits;

#ifdef __Fuchsia__
  // Correct allocated inode count.
  status = CalculateBitsSetBitmap(transaction_handler, device, out_info->ibm_block,
                                  inode_bitmap_num_blocks, &(out_info->alloc_inode_count));
#else
  status = CalculateBitsSetBitmap(transaction_handler, out_info->ibm_block, inode_bitmap_num_blocks,
                                  &(out_info->alloc_inode_count));
#endif

  if (status != ZX_OK) {
    return status;
  }
  return ZX_OK;
}

zx_status_t Fsck(std::unique_ptr<Bcache> bc, const FsckOptions& options,
                 std::unique_ptr<Bcache>* out_bc) {
  std::unique_ptr<MinfsChecker> chk;
  zx_status_t status = MinfsChecker::Create(std::move(bc), options, &chk);
  if (status != ZX_OK) {
    FS_TRACE_ERROR("Fsck: Init failure: %d\n", status);
    return status;
  }

  chk->CheckReserved();

  status = chk->CheckInode(kMinfsRootIno, kMinfsRootIno, 0);
  if (status != ZX_OK) {
    FS_TRACE_ERROR("Fsck: CheckInode failure: %d\n", status);
    return status;
  }

  zx_status_t r;

  // Save an error if it occurs, but check for subsequent errors anyway.
  r = chk->CheckUnlinkedInodes();
  status |= (status != ZX_OK) ? 0 : r;
  r = chk->CheckForUnusedBlocks();
  status |= (status != ZX_OK) ? 0 : r;
  r = chk->CheckForUnusedInodes();
  status |= (status != ZX_OK) ? 0 : r;
  r = chk->CheckLinkCounts();
  status |= (status != ZX_OK) ? 0 : r;
  r = chk->CheckAllocatedCounts();
  status |= (status != ZX_OK) ? 0 : r;

  r = chk->CheckSuperblockIntegrity();
  status |= (status != ZX_OK) ? 0 : r;

  status |= (status != ZX_OK) ? 0 : (chk->conforming_ ? ZX_OK : ZX_ERR_BAD_STATE);
  if (status != ZX_OK) {
    return status;
  }

  if (out_bc != nullptr) {
    *out_bc = MinfsChecker::Destroy(std::move(chk));
  }
  return ZX_OK;
}

}  // namespace minfs