// Copyright 2020 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 "src/storage/minfs/vnode_mapper.h"

#include "src/storage/minfs/lazy_buffer.h"
#include "src/storage/minfs/minfs_private.h"
#include "src/storage/minfs/vnode.h"

namespace minfs {

// A Minfs file looks like:
//
// +-----------------------|-------------------------]------------------------+
// |     direct blocks     |    indirect blocks      | double indirect blocks |
// +-----------------------|-------------------------|------------------------+
// |<--kMinfsDirect (16)-->^<-------- [1] ---------->^<-------- [2] --------->^
//                         |                         |                        |
//                         |                         |                        |
//            kIndirectFileStartBlock                |                        |
//                                  kDoubleIndirectFileStartBlock             |
//                                                                        kMaxBlocks
//
// [1]: kMinfsIndirect (31) * kDirectPerIndirect (2048) = 63488
// [2]: kMinfsDoubleIndirect (1) * kDirectPerIndirect (2048) * kDirectPerIndirect (2048) = 4194304
//
// The pointers to those blocks are arranged like this:
//
//      inode.dnum             inode.inum              inode.dinum
//          |                      |                        |
//          v                      v                        v
//      Data blocks         Indirect blocks      Double indirect blocks
//                                 | (a)                    | (b)
//                                 v                        v
//                           Data blocks             Indirect blocks
//                                                          | (c)
//                                                          v
//                                                     Data blocks
//
// We support up to three *levels* of indirection.
//
// The pointers that aren't stored in an inode are stored in blocks that we need to allocate, and
// are referred to as indirect blocks. These blocks store 2048 block pointers. These blocks of block
// pointers are cached and stored in a VMO backed buffer, also known as the virtual indirect file,
// and it has the following layout:
//
//   +------------------------+----------------------------+--------------------------+
//   |    indirect-leaf (a)   |    double-indirect (b)     | double-indirect-leaf (c) |
//   +------------------------+----------------------------+--------------------------+
//   |<-kMinfsIndirect (31)-->|<-kMinfsDoublyIndirect (1)->|<--------- [1] ---------->|
//
// [1]: kMinfsDoublyIndirect (1) * kMinfsDirectPerIndirect (2048)

namespace {

// These constants are the offsets in terms of block pointers to (b) and (c) above, respectively.
constexpr uint64_t kDoubleIndirectViewStart{static_cast<uint64_t>(kMinfsIndirect) *
                                            kMinfsDirectPerIndirect};
constexpr uint64_t kDoubleIndirectLeafViewStart{kDoubleIndirectViewStart +
                                                static_cast<uint64_t>(kMinfsDoublyIndirect) *
                                                    kMinfsDirectPerIndirect};

// Scans |array| for a contiguous range of blocks of at most |max_blocks|.
uint64_t Coalesce(const blk_t* array, uint64_t max_blocks) {
  uint64_t count = 1;
  if (*array == 0) {
    // A sparse range.
    while (count < max_blocks && array[count] == 0) {
      ++count;
    }
  } else {
    while (count < max_blocks && array[count] == array[count - 1] + 1) {
      ++count;
    }
  }
  return count;
}

// Converts blk_t to DeviceBlock. blk_t represents zeroed/sparse/unmapped blocks differently and are
// relative to |dat_block| in the super-block.
DeviceBlock ToDeviceBlock(VnodeMinfs* vnode, blk_t block) {
  return block == 0 ? DeviceBlock::Unmapped() : DeviceBlock(block + vnode->Vfs()->Info().dat_block);
}

// Returns a flusher responsible for flushing updated block pointers in the inode.
BaseBufferView::Flusher GetDirectFlusher(VnodeMinfs* vnode, PendingWork* transaction) {
  return [vnode, transaction](BaseBufferView* view) {
    vnode->InodeSync(transaction, kMxFsSyncDefault);
    return zx::ok();
  };
}

// Returns a flusher responsible for flushing updated block pointers in indirect blocks;
BaseBufferView::Flusher GetIndirectFlusher(VnodeMinfs* vnode, LazyBuffer* file,
                                           PendingWork* transaction) {
#ifdef __Fuchsia__
  return [vnode, file, transaction](BaseBufferView* view) {
    VnodeIndirectMapper mapper(vnode);
    return file->Flush(
        transaction, &mapper, view,
        [transaction](ResizeableBufferType* buffer, BlockRange range, DeviceBlock device_block) {
          transaction->EnqueueMetadata(
              storage::Operation{
                  .type = storage::OperationType::kWrite,
                  .vmo_offset = range.Start(),
                  .dev_offset = device_block.block(),
                  .length = range.Length(),
              },
              buffer);
          return zx::ok();
        });
  };
#else
  // TODO(https://fxbug.dev/42124749): For the time being, host side code must immediately write data to the
  // device, but we should be able to make this code the same as above if storage::BufferedOperation
  // changes a bit (so that a pointer to the buffer is kept rather than a pointer to the address in
  // memory).
  return [vnode, file, transaction](BaseBufferView* view) {
    VnodeIndirectMapper mapper(vnode);
    auto status = file->Flush(
        transaction, &mapper, view,
        [vnode](ResizeableBufferType* buffer, BlockRange range, DeviceBlock device_block) {
          return EnumerateBlocks(
              range, [vnode, buffer, range, device_block](BlockRange r) -> zx::result<uint64_t> {
                auto status = vnode->Vfs()->GetMutableBcache()->Writeblk(
                    static_cast<blk_t>(device_block.block() + (r.Start() - range.Start())),
                    buffer->Data(r.Start()));
                if (status.is_ok()) {
                  return zx::ok(1);
                } else {
                  return status.take_error();
                }
              });
        });
    return status;
  };
#endif
}

// -- View Getters --
//
// These functions are helpers that set up BufferView objects for ranges of block pointers.

// The dnum block pointers.
zx::result<BufferView<blk_t>> GetInodeDirectView(PendingWork* transaction, VnodeMinfs* vnode,
                                                 BlockPointerRange range) {
  ZX_ASSERT(range.End() <= kMinfsDirect);
  return zx::ok(BufferView<blk_t>(BufferPtr::FromMemory(&vnode->GetMutableInode()->dnum),
                                  range.Start(), range.End() - range.Start(),
                                  transaction ? GetDirectFlusher(vnode, transaction) : nullptr));
}

// The inum block pointers.
zx::result<BufferView<blk_t>> GetInodeIndirectView(PendingWork* transaction, VnodeMinfs* vnode,
                                                   BlockPointerRange range) {
  ZX_ASSERT(range.End() <= kMinfsIndirect);
  return zx::ok(BufferView<blk_t>(BufferPtr::FromMemory(&vnode->GetMutableInode()->inum),
                                  range.Start(), range.End() - range.Start(),
                                  transaction ? GetDirectFlusher(vnode, transaction) : nullptr));
}

// The dinum block pointers.
zx::result<BufferView<blk_t>> GetInodeDoubleIndirectView(PendingWork* transaction,
                                                         VnodeMinfs* vnode,
                                                         BlockPointerRange range) {
  ZX_ASSERT(range.End() <= kMinfsDoublyIndirect);
  return zx::ok(BufferView<blk_t>(BufferPtr::FromMemory(&vnode->GetMutableInode()->dinum),
                                  range.Start(), range.End() - range.Start(),
                                  transaction ? GetDirectFlusher(vnode, transaction) : nullptr));
}

// The pointers in the indirect file. See diagram above to understand how these are laid out.
zx::result<BufferView<blk_t>> GetViewForIndirectFile(PendingWork* transaction, VnodeMinfs* vnode,
                                                     BlockPointerRange range) {
  zx::result<LazyBuffer*> file = vnode->GetIndirectFile();
  if (file.is_error())
    return file.take_error();
  VnodeIndirectMapper mapper(vnode);
  LazyBuffer::Reader reader(vnode->Vfs()->GetMutableBcache(), &mapper, file.value());
  return file.value()->GetView<blk_t>(
      range.Start(), range.End() - range.Start(), &reader,
      transaction ? GetIndirectFlusher(vnode, file.value(), transaction) : nullptr);
}

}  // namespace

// -- VnodeIndirectMapper --

zx::result<DeviceBlockRange> VnodeIndirectMapper::Map(BlockRange range) {
  return MapForWrite(/*transaction=*/nullptr, range, /*allocated=*/nullptr);
}

zx::result<BufferView<blk_t>> VnodeIndirectMapper::GetView(PendingWork* transaction,
                                                           BlockRange range) {
  constexpr uint64_t kDoubleIndirectLeafStart{kMinfsIndirect + kMinfsDoublyIndirect};
  constexpr uint64_t kMax{kDoubleIndirectLeafStart +
                          static_cast<uint64_t>(kMinfsDoublyIndirect) * kMinfsDirectPerIndirect};
  if (range.Start() < kMinfsIndirect) {
    // Region (a) -- Pointers are to be found in the inum field in the inode.
    return GetInodeIndirectView(
        transaction, &vnode_,
        BlockPointerRange(range.Start(),
                          std::min(range.End(), static_cast<uint64_t>(kMinfsIndirect))));
  } else if (range.Start() < kDoubleIndirectLeafStart) {
    // Region (b) -- Pointers are to be found in the dinum field in the inode.
    return GetInodeDoubleIndirectView(
        transaction, &vnode_,
        BlockPointerRange(range.Start() - kMinfsIndirect,
                          std::min(range.End(), kDoubleIndirectLeafStart) - kMinfsIndirect));
  } else if (range.Start() < kMax) {
    // Region (c) -- Pointers are to be found in region (b) of the virtual indirect file.
    return GetViewForIndirectFile(
        transaction, &vnode_,
        BlockPointerRange(
            range.Start() - kDoubleIndirectLeafStart + kDoubleIndirectViewStart,
            std::min(range.End(), kMax) - kDoubleIndirectLeafStart + kDoubleIndirectViewStart));
  } else {
    return zx::error(ZX_ERR_OUT_OF_RANGE);
  }
}

zx::result<DeviceBlockRange> VnodeIndirectMapper::MapForWrite(PendingWork* transaction,
                                                              BlockRange range, bool* allocated) {
  BufferView<blk_t> view;
  if (auto view_or = GetView(transaction, range); view_or.is_error()) {
    return view_or.take_error();
  } else {
    view = std::move(view_or).value();
  }
  // If |allocated| is non-null, allocate an indirect block if necessary.
  uint64_t block_count;
  if (*view == 0 && allocated) {
    block_count = 1;
    blk_t new_block = 0;
    vnode_.AllocateIndirect(transaction, &new_block);
    ZX_ASSERT(new_block != 0);
    view.mut_ref() = new_block;
    *allocated = true;
    auto status = view.Flush();
    if (status.is_error())
      return status.take_error();
  } else {
    if (allocated)
      *allocated = false;
    block_count = Coalesce(view.data(), view.count());
  }
  return zx::ok(DeviceBlockRange(ToDeviceBlock(&vnode_, *view), block_count));
}

// -- VnodeMapper --

zx::result<std::pair<blk_t, uint64_t>> VnodeMapper::MapToBlk(BlockRange range) {
  VnodeIterator iterator;
  auto status = iterator.Init(this, nullptr, range.Start());
  if (status.is_error())
    return status.take_error();
  return zx::ok(std::make_pair(iterator.Blk(), iterator.GetContiguousBlockCount(range.Length())));
}

zx::result<DeviceBlockRange> VnodeMapper::Map(BlockRange range) {
  zx::result<std::pair<blk_t, uint64_t>> status = MapToBlk(range);
  if (status.is_error())
    return status.take_error();
  return zx::ok(
      DeviceBlockRange(ToDeviceBlock(&vnode_, status.value().first), status.value().second));
}

// -- VnodeIterator --

zx::result<> VnodeIterator::Init(VnodeMapper* mapper, PendingWork* transaction,
                                 uint64_t file_block) {
  mapper_ = mapper;
  transaction_ = transaction;
  file_block_ = file_block;
  contiguous_block_count_ = 0;
  // The file block determines the number of levels of views that we need, and the view-getters
  // that we need to use.
  if (file_block < VnodeMapper::kIndirectFileStartBlock) {
    // We only need the dnum pointers.
    level_count_ = 1;
    auto status =
        InitializeLevel(0, BlockPointerRange(0, kMinfsDirect), file_block, &GetInodeDirectView);
    if (status.is_error())
      return status;
  } else if (file_block < VnodeMapper::kDoubleIndirectFileStartBlock) {
    // We need the inum pointers and the blocks they point to.
    level_count_ = 2;
    uint64_t relative_block = file_block - VnodeMapper::kIndirectFileStartBlock;
    auto status = InitializeLevel(1, BlockPointerRange(0, kMinfsIndirect),
                                  relative_block / kMinfsDirectPerIndirect, &GetInodeIndirectView);
    if (status.is_error())
      return status;
    status = InitializeIndirectLevel(0, relative_block);
    if (status.is_error())
      return status;
  } else if (file_block < VnodeMapper::kMaxBlocks) {
    // We need the dinum pointers and two more levels.
    level_count_ = 3;
    uint64_t relative_block = file_block - VnodeMapper::kDoubleIndirectFileStartBlock;
    auto status =
        InitializeLevel(2, BlockPointerRange(0, kMinfsDoublyIndirect),
                        relative_block / kMinfsDirectPerIndirect / kMinfsDirectPerIndirect,
                        &GetInodeDoubleIndirectView);
    if (status.is_error())
      return status;
    status = InitializeIndirectLevel(
        1, relative_block / kMinfsDirectPerIndirect + kDoubleIndirectViewStart);
    if (status.is_error())
      return status;
    status = InitializeIndirectLevel(0, relative_block + kDoubleIndirectLeafViewStart);
    if (status.is_error())
      return status;
  } else if (file_block == VnodeMapper::kMaxBlocks) {
    // Allow the iterator to point at the end.
    level_count_ = 0;
  } else {
    return zx::error(ZX_ERR_OUT_OF_RANGE);
  }
  return zx::ok();
}

// Here |range| and |block| are blocks relative to the base of the pointers we are looking at, which
// could be the dnum, inum, dinum pointers or the pointers in the virtual indirect file. |block|
// must be contained within |range|.
zx::result<> VnodeIterator::InitializeLevel(int level, BlockPointerRange range, uint64_t block,
                                            ViewGetter view_getter) {
  ZX_ASSERT(block >= range.Start() && block < range.End());
  levels_[level].range = range;
  levels_[level].count = range.End() - range.Start();
  levels_[level].index = block - range.Start();
  // If the parent level is sparse, delay getting the view until we need to.
  if (level + 1 < level_count_ && levels_[level + 1].blk() == 0) {
    levels_[level].view = {};
    levels_[level].view_getter = std::move(view_getter);
  } else {
    zx::result<BufferView<blk_t>> view = view_getter(transaction_, &mapper_->vnode(), range);
    if (view.is_error())
      return view.take_error();
    levels_[level].view = std::move(view).value();
    levels_[level].view_getter = nullptr;
  }
  return zx::ok();
}

// Convenience function for levels that point to the virtual indirect file. Here |relative_block| is
// the pointer offset within the virtual indirect file.
zx::result<> VnodeIterator::InitializeIndirectLevel(int level, uint64_t relative_block) {
  uint64_t first_block = fbl::round_down(relative_block, kMinfsDirectPerIndirect);
  return InitializeLevel(level,
                         BlockPointerRange(first_block, first_block + kMinfsDirectPerIndirect),
                         relative_block, &GetViewForIndirectFile);
}

zx::result<> VnodeIterator::SetBlk(Level* level, blk_t block) {
  ZX_ASSERT(level_count_ > 0);
  // If this level is sparse, try and get a view for it now.
  if (level->IsSparse()) {
    if (block == 0)
      return zx::ok();
    zx::result<BufferView<blk_t>> view =
        level->view_getter(transaction_, &mapper_->vnode(), level->range);
    if (view.is_error())
      return view.take_error();
    level->view = std::move(view).value();
  }
  level->view.mut_ref(level->index) = block;
  return zx::ok();
}

uint64_t VnodeIterator::GetContiguousBlockCount(uint64_t max_blocks) const {
  if (level_count_ == 0)
    return 0;
  if (contiguous_block_count_ == 0)
    contiguous_block_count_ = ComputeContiguousBlockCount();
  return std::min(contiguous_block_count_, max_blocks);
}

uint64_t VnodeIterator::ComputeContiguousBlockCount() const {
  // For efficiency reasons, handle sparse ranges differently. This is so we can quickly scan the
  // (typically) unallocated/sparse blocks from the end of the file.
  if (Blk() == 0) {
    // The number of blocks we have found so far.
    uint64_t count = 0;
    // The number of blocks a block pointer represents at the current level.
    uint64_t multiplier = 1;
    // The index into the view for the current level.
    uint64_t index = levels_[0].index;
    int level = 0;
    // N.B. When we truncate blocks, we rely on the fact that we only go *up* the tree here, *not*
    // down. To further explain, consider the case where the inode points to an indirect block, but
    // the indirect block doesn't happen to have any blocks allocated. We could, in theory, coalesce
    // those blocks and just say it's all sparse, but if we did that, we wouldn't free the indirect
    // block. Instead, we'll coalesce as many blocks as we can at the lowest level, then move up a
    // level and coalesce all the blocks at that level, but we'll stop as soon as we find an
    // allocated block, even though that indirect block might not point to any allocated blocks.
    for (;;) {
      const uint64_t left = levels_[level].count - index;
      if (left == 0 || levels_[level].IsSparse()) {
        count += left * multiplier;
      } else if (levels_[level].view[index] == 0) {
        uint64_t contiguous = Coalesce(&levels_[level].view[index], left);
        count += contiguous * multiplier;
        if (contiguous < left)
          return count;
      } else {
        // We've come to a block that isn't sparse.
        return count;
      }
      if (++level >= level_count_)
        return count;
      multiplier *= kMinfsDirectPerIndirect;
      index = levels_[level].index + 1;
    }
  } else {
    return Coalesce(&levels_[0].view[levels_[0].index], levels_[0].remaining());
  }
}

zx::result<> VnodeIterator::FlushLevel(int level) {
  if (!transaction_)
    return zx::ok();
  if (level + 1 < level_count_) {
    const blk_t parent_block = levels_[level + 1].blk();
    // If this block is now empty and we have a parent, deallocate rather than writing block. As an
    // optimisation, we quickly check that item current pointed at is zero before doing a full check
    // of the whole block.
    if (parent_block != 0 && levels_[level].blk() == 0) {
      ZX_ASSERT(levels_[level].view.count() == kMinfsDirectPerIndirect);
      bool empty = true;
      for (unsigned i = 0; i < kMinfsDirectPerIndirect; ++i) {
        if (levels_[level].view[i] != 0) {
          empty = false;
          break;
        }
      }
      if (empty) {
        // Delete the block and update the parent.
        mapper_->vnode().DeleteBlock(transaction_, 0, parent_block, /*indirect=*/true);
        [[maybe_unused]] auto status = SetBlk(&levels_[level + 1], 0);
        levels_[level].view.set_dirty(false);
        return zx::ok();
      }
    }
    // If there are modifications and the parent doesn't have a block, allocate it now. This isn't
    // strictly necessary because VnodeIndirectMapper will allocate if it needs to. However, it will
    // immediately flush whereas if we do it here, we can delay the flush as there might be more
    // changes to make later.
    if (levels_[level].view.dirty() && parent_block == 0) {
      blk_t new_block;
      mapper_->vnode().AllocateIndirect(transaction_, &new_block);
      ZX_ASSERT(new_block != 0);
      [[maybe_unused]] auto status = SetBlk(&levels_[level + 1], new_block);
    }
  }
  return levels_[level].view.Flush();
}

zx::result<> VnodeIterator::Flush() {
  if (!transaction_)
    return zx::ok();  // Iterator is read-only.
  for (int level = 0; level < level_count_; ++level) {
    auto status = FlushLevel(level);
    if (status.is_error())
      return status;
  }
  return zx::ok();
}

zx::result<> VnodeIterator::Advance(const uint64_t advance) {
  if (level_count_ == 0) {
    return advance == 0 ? zx::ok() : zx::make_result(ZX_ERR_BAD_STATE);
  }
  // Short circuit for the common case.
  if (advance < levels_[0].remaining()) {
    levels_[0].index += advance;
    file_block_ += advance;
    if (advance >= contiguous_block_count_) {
      contiguous_block_count_ = 0;
    } else {
      contiguous_block_count_ -= advance;
    }
    return zx::ok();
  }
  // Get a new iterator for the new file block.
  VnodeIterator iterator;
  auto status = iterator.Init(mapper_, transaction_, file_block_ + advance);
  if (status.is_error())
    return status;
  // Now see which of the old views need flushing.
  if (iterator.level_count_ != level_count_) {
    // The level count is different so we flush all of the levels.
    status = Flush();
    if (status.is_error())
      return status;
  } else {
    // If the two iterators have the same view for a level, just move the view. This prevents us
    // from over-flushing.
    for (int level = 0; level < level_count_; ++level) {
      if (levels_[level].range == iterator.levels_[level].range) {
        // The ranges are the same and because the level count is the same, we know that the view
        // must point to the same thing, so we can just move the views over and defer flushing this
        // level.
        iterator.levels_[level].view = std::move(levels_[level].view);
      } else {
        status = FlushLevel(level);
        if (status.is_error())
          return status;
      }
    }
  }
  *this = std::move(iterator);
  return zx::ok();
}

}  // namespace minfs