// Copyright 2018 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 ZIRCON_SYSTEM_ULIB_BLOBFS_ALLOCATOR_ALLOCATOR_H_
#define ZIRCON_SYSTEM_ULIB_BLOBFS_ALLOCATOR_ALLOCATOR_H_

#include <fuchsia/blobfs/llcpp/fidl.h>
#include <inttypes.h>
#include <lib/fzl/resizeable-vmo-mapper.h>
#include <lib/zx/vmo.h>
#include <stdbool.h>
#include <stdint.h>
#include <zircon/types.h>

#include <optional>

#include <bitmap/raw-bitmap.h>
#include <bitmap/rle-bitmap.h>
#include <blobfs/common.h>
#include <blobfs/format.h>
#include <blobfs/node-finder.h>
#include <fbl/algorithm.h>
#include <fbl/function.h>
#include <fbl/vector.h>
#include <fs/trace.h>
#include <fs/transaction/legacy_transaction_handler.h>
#include <id_allocator/id_allocator.h>
#include <storage/buffer/vmoid_registry.h>

#include "extent-reserver.h"
#include "node-reserver.h"

namespace blobfs {

struct BlockRegion {
  uint64_t offset;
  uint64_t length;
};

// An interface which controls actual access to the underlying storage.
class SpaceManager : public storage::VmoidRegistry {
 public:
  virtual ~SpaceManager() = default;

  virtual const Superblock& Info() const = 0;

  // Adds any number of nodes to |node_map|, extending the volume if necessary.
  virtual zx_status_t AddInodes(fzl::ResizeableVmoMapper* node_map) = 0;

  // Adds space for |nblocks| blocks to |map|, extending the volume if necessary.
  virtual zx_status_t AddBlocks(uint64_t nblocks, RawBitmap* map) = 0;
};

// Allocates and frees both block and node entries.
//
// Also maintains reservation mappings, to help in-progress allocations avoid
// from being persisted too early.
class Allocator : private ExtentReserver, private NodeReserver, public NodeFinder {
 public:
  Allocator(SpaceManager* space_manager, RawBitmap block_map, fzl::ResizeableVmoMapper node_map,
            std::unique_ptr<id_allocator::IdAllocator> nodes_bitmap);
  ~Allocator();

  using ExtentReserver::ReservedBlockCount;
  using NodeReserver::ReservedNodeCount;

  ////////////////
  // blobfs::NodeFinder interface.
  //
  // TODO(smklein): It may be possible to convert NodeFinder from an interface
  // to a concrete base class if we can reconcile the differences with host.

  Inode* GetNode(uint32_t node_index) final;

  ////////////////
  // Other interfaces.

  void SetLogging(bool enable) { log_allocation_failure_ = enable; }

  // 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_unset = nullptr) const;

  // Reads the block map and node map from underlying storage, using a
  // blocking read transaction.
  //
  // It is unsafe to call this method while any nodes or blocks are reserved.
  zx_status_t ResetFromStorage(fs::ReadTxn txn);

  // Provides a read-only view into the block map.
  const zx::vmo& GetBlockMapVmo() const;

  // Provides a read-only view into the node map.
  const zx::vmo& GetNodeMapVmo() 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, fbl::Vector<ReservedExtent>* out_extents);

  // Marks blocks as allocated which have previously been reserved to the bitmap.
  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.
  void 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, fbl::Vector<ReservedNode>* out_nodes);

  // Reserves a nodes for allocation (in-memory).
  std::optional<ReservedNode> ReserveNode();

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

  // Marks a reserved node by updating the node map to indicate it is an
  // allocated extent container
  void MarkContainerNodeAllocated(const ReservedNode& node, uint32_t previous_node);

  // 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.
  void FreeNode(uint32_t node_index);

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

 private:
  // Resets the size of the block map based on |Info().data_block_count|.
  //
  // It is unsafe to call this method while any blocks are reserved.
  zx_status_t ResetBlockMapSize();

  // Resets the size of the node map based on |Info().inode_count|.
  //
  // It is unsafe to call this method while any nodes are reserved.
  zx_status_t ResetNodeMapSize();

  // 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,
                              fbl::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);

  // Searches for |nblocks| 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,
                         fbl::Vector<ReservedExtent>* out_extents, uint64_t* out_actual_blocks);

  zx_status_t FindNode(uint32_t* node_index_out);

  void LogAllocationFailure(uint64_t num_blocks) const;

  // Grow allocator
  zx_status_t Grow();

  SpaceManager* space_manager_;

  RawBitmap block_map_ = {};
  fzl::ResizeableVmoMapper node_map_;
  std::unique_ptr<id_allocator::IdAllocator> node_bitmap_;

  bool log_allocation_failure_ = true;
};

}  // namespace blobfs

#endif  // ZIRCON_SYSTEM_ULIB_BLOBFS_ALLOCATOR_ALLOCATOR_H_