src/storage/blobfs/allocator/base_allocator.h

// Copyright 2021 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef SRC_STORAGE_BLOBFS_ALLOCATOR_BASE_ALLOCATOR_H_
#define SRC_STORAGE_BLOBFS_ALLOCATOR_BASE_ALLOCATOR_H_

#include <lib/stdcompat/span.h>

#include <cstdint>
#include <vector>

#include <bitmap/raw-bitmap.h>
#include <id_allocator/id_allocator.h>

#include "src/storage/blobfs/allocator/extent_reserver.h"
#include "src/storage/blobfs/allocator/node_reserver.h"
#include "src/storage/blobfs/common.h"
#include "src/storage/blobfs/format.h"
#include "src/storage/blobfs/node_finder.h"

namespace blobfs {

struct BlockRegion {
  uint64_t offset;
  uint64_t length;
};

// Base class for managing the blobfs block bitmap and node allocations. Allows for reserving blocks
// and nodes without updating the allocations so the reservations are not persisted prematurely.
class BaseAllocator : private ExtentReserver, private NodeReserverInterface, public NodeFinder {
 public:
  using ExtentReserver::ReservedBlockCount;

  BaseAllocator(RawBitmap block_bitmap, std::unique_ptr<id_allocator::IdAllocator> node_bitmap);

  ~BaseAllocator() override = default;

  // Returns true if [start_block, end_block) is allocated.
  //
  // If any blocks are unallocated, will set the optional output parameter |out_first_unset| to
  // the first unallocated block within this range.
  bool CheckBlocksAllocated(uint64_t start_block, uint64_t end_block,
                            uint64_t* out_first_unallocated = nullptr) const;

  // Returns true if the block is allocated. If the block_number is invalid, returns error.
  zx::result<bool> IsBlockAllocated(uint64_t block_number) const;

  // Reserves space for blocks in memory. Does not update disk.
  //
  // On success, appends the (possibly non-contiguous) region of allocated blocks to |out_extents|.
  // On failure, |out_extents| is cleared.
  zx_status_t ReserveBlocks(uint64_t num_blocks, std::vector<ReservedExtent>* out_extents);

  // Marks blocks as allocated which have previously been reserved.
  void MarkBlocksAllocated(const ReservedExtent& reserved_extent);

  // Frees blocks which have already been allocated (in-memory).
  //
  // |extent| must represent a portion of the block map which has already been allocated.  Returns a
  // ReservedExtent which keeps the blocks reserved until destroyed (which allows us to hold the
  // blocks until the transaction commits).
  ReservedExtent FreeBlocks(const Extent& extent);

  // Reserves space for nodes in memory. Does not update disk.
  //
  // On success, appends the (possibly non-contiguous) nodes to |out_nodes|. On failure, |out_nodes|
  // is cleared.
  zx_status_t ReserveNodes(uint64_t num_nodes, std::vector<ReservedNode>* out_nodes);

  // blobfs::NodeReserverInterface interface.
  zx::result<ReservedNode> ReserveNode() override;
  void UnreserveNode(ReservedNode node) override;
  uint64_t ReservedNodeCount() const override;

  // Marks a reserved node by updating the node map to indicate it is an allocated inode.
  void MarkInodeAllocated(ReservedNode node);

  // Marks a reserved node by updating the node map to indicate it is an allocated extent container.
  // Makes |node| follow |previous_node_index| in the extent container list.
  zx_status_t MarkContainerNodeAllocated(ReservedNode node, uint32_t previous_node_index);

  // Mark a node allocated. The node may or may not be reserved.
  void MarkNodeAllocated(uint32_t node_index);

  // Frees a node which has already been committed. Returns an error if the node could not be freed.
  zx_status_t FreeNode(uint32_t node_index);

  // Record the location and size of all non-free block regions.
  std::vector<BlockRegion> GetAllocatedRegions() const;

 protected:
  // Requests that blobfs increase the size of it's data section by |block_count| blocks.
  virtual zx::result<> AddBlocks(uint64_t block_count) = 0;

  // Requests that blobfs increase the size of it's node map.
  virtual zx::result<> AddNodes() = 0;

  RawBitmap& GetBlockBitmap() { return block_bitmap_; }
  const RawBitmap& GetBlockBitmap() const { return block_bitmap_; }
  id_allocator::IdAllocator& GetNodeBitmap() { return *node_bitmap_; }
  const id_allocator::IdAllocator& GetNodeBitmap() const { return *node_bitmap_; }

 private:
  // Returns true if [start_block, end_block) are unallocated.
  bool CheckBlocksUnallocated(uint64_t start_block, uint64_t end_block) const;

  // Avoids a collision with the committed block map, moving the starting location / block length to
  // find a region with no collision.
  //
  // Returns true if we should restart searching to attempt to maximally munch from the allocation
  // pool.
  bool FindUnallocatedExtent(uint64_t start, uint64_t block_length, uint64_t* out_start,
                             uint64_t* out_block_length);

  // Identifies the subset of blocks which don't collide with pending reservations. If any
  // collisions exist, maximally munches the available free space into newly reserved extents.
  //
  // It is assumed that [start, start + block_length) is unallocated; this is internally asserted.
  // |FindUnallocatedExtent| should be invoked first to provide this guarantee.
  //
  // Returns true if we should restart searching to attempt to maximally munch from the allocation
  // pool. Otherwise, no collisions with pending reservations exist.
  bool MunchUnreservedExtents(bitmap::RleBitmap::const_iterator reserved_iterator,
                              uint64_t remaining_blocks, uint64_t start, uint64_t block_length,
                              std::vector<ReservedExtent>* out_extents,
                              bitmap::RleBitmap::const_iterator* out_reserved_iterator,
                              uint64_t* out_remaining_blocks, uint64_t* out_start,
                              uint64_t* out_block_length) __TA_REQUIRES(mutex());

  // Searches for |num_blocks| free blocks between the block_map_ and reserved_blocks_ bitmaps.
  //
  // Appends the (possibly non-contiguous) region of allocated blocks to |out_extents|.
  //
  // May fail if not enough blocks can be found. In this case, an error will be returned, and the
  // number of found blocks will be returned in |out_actual_blocks|. This result is guaranteed to be
  // less than or equal to |num_blocks|.
  zx_status_t FindBlocks(uint64_t start, uint64_t num_blocks,
                         std::vector<ReservedExtent>* out_extents, uint64_t* out_actual_blocks);

  // Finds an unallocated node.
  zx::result<uint32_t> FindNode();

  // The number of nodes currently reserved.
  uint64_t reserved_node_count_ = 0;
  RawBitmap block_bitmap_;
  std::unique_ptr<id_allocator::IdAllocator> node_bitmap_;
};

}  // namespace blobfs

#endif  // SRC_STORAGE_BLOBFS_ALLOCATOR_BASE_ALLOCATOR_H_