src/storage/minfs/vnode_mapper.cc - fuchsia - Git at Google

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