src/storage/minfs/vnode_mapper.h

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

#ifndef SRC_STORAGE_MINFS_VNODE_MAPPER_H_
#define SRC_STORAGE_MINFS_VNODE_MAPPER_H_

#include <array>

#include <range/range.h>

#include "src/storage/minfs/buffer_view.h"
#include "src/storage/minfs/lazy_reader.h"
#include "src/storage/minfs/pending_work.h"

namespace minfs {

class VnodeIterator;
class VnodeMinfs;

// Used to represent ranges of block pointers that can be in dnum, inum, dinum fields within the
// inode (corresponding to the direct, indirect and double indirect block pointers) or the pointers
// within the virtual indirect file.
class BlockPointerRange : public range::Range<uint64_t> {
 public:
  using range::Range<uint64_t>::Range;
};

// Maps from file to device blocks for the virtual indirect block file, which contains the leaf
// indirect blocks pointers, double indirect block pointers and leaf double indirect pointers. See
// the comment in the implementation file for a more detailed explanation.
class VnodeIndirectMapper : public MapperInterface {
 public:
  explicit VnodeIndirectMapper(VnodeMinfs* vnode) : vnode_(*vnode) {}

  [[nodiscard]] zx::result<DeviceBlockRange> Map(BlockRange range) override;

  [[nodiscard]] zx::result<DeviceBlockRange> MapForWrite(PendingWork* transaction, BlockRange range,
                                                         bool* allocated) override;

 private:
  // Returns a view into the indirect file for the blocks in |range|.
  zx::result<BufferView<blk_t>> GetView(PendingWork* transaction, BlockRange range);

  VnodeMinfs& vnode_;
};

// A mapper for a Minfs vnode, responsible for mapping from file blocks to device blocks.
class VnodeMapper : public MapperInterface {
 public:
  static constexpr uint64_t kIndirectFileStartBlock = kMinfsDirect;
  static constexpr uint64_t kDoubleIndirectFileStartBlock =
      kMinfsDirect + kMinfsDirectPerIndirect * kMinfsIndirect;
  static constexpr uint64_t kMaxBlocks =
      kDoubleIndirectFileStartBlock + kMinfsDirectPerDindirect * kMinfsDoublyIndirect;

  explicit VnodeMapper(VnodeMinfs* vnode) : vnode_(*vnode) {}

  VnodeMinfs& vnode() { return vnode_; }

  // MapperInterface:

  zx::result<DeviceBlockRange> Map(BlockRange range) override;

  zx::result<DeviceBlockRange> MapForWrite(PendingWork* transaction, BlockRange file_range,
                                           bool* allocated) override {
    // All allocations for Minfs vnodes are done elsewhere.
    return zx::error(ZX_ERR_NOT_SUPPORTED);
  }

  // A convenience function that does the same as Map but returns a blk_t.
  [[nodiscard]] zx::result<std::pair<blk_t, uint64_t>> MapToBlk(BlockRange range);

 private:
  VnodeMinfs& vnode_;
};

// Iterator that keeps track of block pointers for a given file block. Depending on the file
// block, there can be up to three levels of block pointers.
//
// Example use, reading a range of blocks:
//
//   VnodeMapper mapper(vnode);
//   VnodeIterator iterator;
//   zx_status_t status = iterator.Init(&mapper, /*transaction=*/nullptr, start_block);
//   if (status != ZX_OK)
//     return status;
//   while (block_count > 0) {
//     blk_t block = iterator.Blk();
//     uint64_t count = iterator.GetContiguousBlockCount(block_count);
//     if (block) {
//       status = ReadBlocks(buffer, iterator.file_block(), block, count);
//       if (status != ZX_OK)
//         return status;
//     } else {
//       ZeroBlocks(buffer, iterator.file_block(), count);
//     }
//     status = iterator.Advance(count);
//     if (status != ZX_OK)
//       return status;
//     block_count -= count;
//   }
class VnodeIterator {
 public:
  // Users must call Init before the iterator is usable. Behaviour is undefined if any methods,
  // except the destructor, are called before Init has successfully returned.
  VnodeIterator() = default;

  // Movable but not copyable.
  VnodeIterator(VnodeIterator&&) = default;
  VnodeIterator& operator=(VnodeIterator&&) = default;

  // Initialize the iterator so that it is pointing at file_block. |transaction| can be nullptr in
  // which case the returned iterator is read-only. The iterator is left in an undefined state if
  // Init fails (except that it is safe to destroy).
  [[nodiscard]] zx::result<> Init(VnodeMapper* mapper, PendingWork* transaction,
                                  uint64_t file_block);

  // Returns the file block that the iterator is currently located at.
  uint64_t file_block() const { return file_block_; }

  // Returns the target block as a blk_t. Zero is special and means the block is unmapped/sparse.
  blk_t Blk() const {
    return level_count_ > 0 && levels_[0].remaining() > 0 ? levels_[0].blk() : 0;
  }

  // Sets the target block. The iterator will need to be flushed after calling this (by calling the
  // Flush method).
  [[nodiscard]] zx::result<> SetBlk(blk_t block) { return SetBlk(levels_.data(), block); }

  // Returns the length in blocks of a contiguous range at most |max_blocks|. For
  // efficiency/simplicity reasons, it might return fewer than there actually are.
  uint64_t GetContiguousBlockCount(
      uint64_t max_blocks = std::numeric_limits<uint64_t>::max()) const;

  // Flushes any changes that may have been made. This is a no-op if there are no changes or
  // this iterator is read-only.
  [[nodiscard]] zx::result<> Flush();

  // Advances the iterator by |advance| blocks. This will also flush the iterator first if
  // necessary.
  [[nodiscard]] zx::result<> Advance(uint64_t advance = 1);

 private:
  using ViewGetter = fit::function<zx::result<BufferView<blk_t>>(PendingWork*, VnodeMinfs* vnode,
                                                                 BlockPointerRange)>;

  // Level contains all the information required to manage block pointers at one particular
  // level. The iterator might need up to three levels of pointers to describe a particular
  // location. For example, if the block is in the double indirect region of the file, there will be
  // a pointer in the inode which points to an indirect block which contains another pointer to
  // another indirect block which has the pointer to the data block. Level holds a view to the bank
  // of pointers for each level.
  struct Level {
    // The number of remaining block pointers for this level.
    size_t remaining() const { return count - index; }
    // The target block as a blk_t.
    blk_t blk() const { return view.IsValid() ? view[index] : 0; }
    // This level could be sparse which means that there is no block allocated at the parent
    // level e.g. this level is for the leaf indirect block pointers and inum[indirect_index] == 0.
    bool IsSparse() const { return !view.IsValid(); }

    // A view to the block pointers for this level.
    BufferView<blk_t> view;
    // The current index on this level.
    size_t index = 0;
    // The number of pointers at this level.
    size_t count = 0;
    // The range of block pointers the view covers. These blocks are relative to the bank of
    // pointers, either the dnum, inum or dinum pointers, or the pointers in the virtual indirect
    // file.
    BlockPointerRange range = {0, 0};
    // A callback to get a view for this level to be used if necessary.
    ViewGetter view_getter;
  };

  // Worst case: double indirect (in inode) -> indirect -> indirect. See the comment at the top of
  // the implementation file for more detail.
  static constexpr int kMaxLevels = 3;

  zx::result<> InitializeLevel(int level, BlockPointerRange range, uint64_t block,
                               ViewGetter view_getter);
  zx::result<> InitializeIndirectLevel(int level, uint64_t relative_block);

  // Flushes the given level if there are any changes.
  [[nodiscard]] zx::result<> FlushLevel(int level);

  // Finds a contiguous run of blocks, but not necessarily the longest.
  uint64_t ComputeContiguousBlockCount() const;

  // Sets a block pointer in the given level.
  zx::result<> SetBlk(Level* level, blk_t block);

  // The owning mapper.
  VnodeMapper* mapper_ = nullptr;
  // A transaction to be used for allocations, or nullptr if read-only.
  PendingWork* transaction_ = nullptr;
  // The current file block that the iterator is pointing at.
  uint64_t file_block_ = 0;
  // The cached contiguous length returned by GetContiguousBlockCount().
  mutable uint64_t contiguous_block_count_ = 0;
  // The number of levels this iterator currently has.
  int level_count_ = 0;
  // The level information.
  std::array<Level, kMaxLevels> levels_;
};

}  // namespace minfs

#endif  // SRC_STORAGE_MINFS_VNODE_MAPPER_H_