blob: 336faee1695254f8cee84188c7f8a7fd1b5ba378 [file] [log] [blame]
// 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.
// This file describes the structure used to allocate
// from an on-disk bitmap.
#include <lib/fit/function.h>
#include <memory>
#include <mutex>
#include <bitmap/raw-bitmap.h>
#include <bitmap/rle-bitmap.h>
#include <bitmap/storage.h>
#include <fbl/macros.h>
#include "src/lib/storage/vfs/cpp/transaction/buffered_operations_builder.h"
#include "src/storage/minfs/allocator/allocator_reservation.h"
#include "src/storage/minfs/allocator/storage.h"
#include "src/storage/minfs/format.h"
#include "src/storage/minfs/superblock.h"
#include "src/storage/minfs/writeback.h"
namespace minfs {
#ifdef __Fuchsia__
using RawBitmap = bitmap::RawBitmapGeneric<bitmap::VmoStorage>;
struct BlockRegion {
uint64_t offset;
uint64_t length;
using RawBitmap = bitmap::RawBitmapGeneric<bitmap::DefaultStorage>;
class Allocator;
// An empty key class which represents the |AllocatorReservation|'s access to
// restricted |Allocator| interfaces.
class AllocatorReservationKey {
// Not copyable or movable
AllocatorReservationKey(const AllocatorReservationKey&) = delete;
AllocatorReservationKey& operator=(const AllocatorReservationKey&) = delete;
AllocatorReservationKey(AllocatorReservationKey&&) = delete;
AllocatorReservationKey& operator=(AllocatorReservationKey&&) = delete;
friend AllocatorReservation;
AllocatorReservationKey() {}
// PendingChange tracks pending allocations and will prevent elements from being allocated twice.
// After a change has been committed (passed to a transaction), deallocated elements can still be
// reserved until the transaction actually writes the transaction to the journal. This is because we
// want to prevent data writes going to those blocks until after that.
// There can be multiple PendingChange objects per transaction, but, at time of writing, there is
// only one PendingChange for allocations and one PendingChange for deallocations for each allocator
// we support (blocks and inodes), so that's 4 per transaction in total.
// This class is not thread-safe and should only be accessed by Allocator, under its lock.
class PendingChange {
enum class Kind { kAllocation, kDeallocation };
// Not copyable or movable.
PendingChange(const PendingChange&) = delete;
PendingChange& operator=(const PendingChange&) = delete;
Kind kind() const { return kind_; }
// The change is committed when the change has been made to the persistent bitmap.
bool is_committed() const { return committed_; }
void set_committed(bool v) { committed_ = v; }
// Returns the number of items that need to be reserved for this change. Reserved is where the
// bitmap indicates the items are free, but they can't be used for some reason.
size_t GetReservedCount() const;
// Returns the next unreserved item starting from |start|.
size_t GetNextUnreserved(size_t start) const;
// Returns the number of items this change covers.
size_t item_count() const { return bitmap_.num_bits(); }
// Access to the underlying bitmap.
bitmap::RleBitmap& bitmap() { return bitmap_; }
PendingChange(Allocator* allocator, Kind kind);
Allocator& allocator_;
const Kind kind_;
// The bitmap keeps track of the changes, one bit per element. If kind_ == Kind::kAllocation, each
// bit is an element to be allocated. If kind_ == Kind::kDeallocation, each bit is an element to
// be deallocated.
bitmap::RleBitmap bitmap_;
// Whether this change is committed to the persistent bitmap.
bool committed_ = false;
class PendingAllocations : public PendingChange {
PendingAllocations(Allocator* allocator) : PendingChange(allocator, Kind::kAllocation) {}
class PendingDeallocations : public PendingChange {
PendingDeallocations(Allocator* allocator) : PendingChange(allocator, Kind::kDeallocation) {}
// The Allocator class is used to abstract away the mechanism by which minfs
// allocates objects internally.
// This class is thread-safe. However, it is worth pointing out a peculiarity regarding queued
// operations: This class enqueues operations to a caller-supplied BufferedOperationsBuilder as they
// are necessary, but the source of these enqueued buffers may change later. If a caller delays
// writeback, it is their responsibility to ensure no concurrent mutable methods of Allocator are
// accessed while issuing the requests, as these methods may put the buffer-to-be-written in an
// inconsistent state.
class Allocator {
virtual ~Allocator();
Allocator(const Allocator&) = delete;
Allocator& operator=(const Allocator&) = delete;
static zx::result<std::unique_ptr<Allocator>> Create(fs::BufferedOperationsBuilder* builder,
std::unique_ptr<AllocatorStorage> storage);
// Return the number of total available elements, after taking reservations into account.
size_t GetAvailable() const __TA_EXCLUDES(lock_);
// Returns the number of reserved blocks.
size_t GetReserved() const __TA_EXCLUDES(lock_);
// Free an item from the allocator.
void Free(AllocatorReservation* reservation, size_t index) __TA_EXCLUDES(lock_);
#ifdef __Fuchsia__
// Extract a vector of all currently allocated regions in the filesystem.
fbl::Vector<BlockRegion> GetAllocatedRegions() const __TA_EXCLUDES(lock_);
// Returns |true| if |index| is allocated. Returns |false| otherwise.
bool CheckAllocated(size_t index) const __TA_EXCLUDES(lock_);
// AllocatorReservation Methods:
// The following methods are restricted to AllocatorReservation via the passkey
// idiom. They are public, but require an empty |AllocatorReservationKey|.
// Allocate a single element and return its newly allocated index.
size_t Allocate(AllocatorReservationKey, AllocatorReservation* reservation) __TA_EXCLUDES(lock_);
// Reserve |count| elements. This is required in order to later allocate them.
// Outputs a |reservation| which contains reservation details.
zx::result<> Reserve(AllocatorReservationKey, PendingWork* transaction, size_t count)
// Unreserve |count| elements. This may be called in the event of failure, or if we
// over-reserved initially.
// PRECONDITION: AllocatorReservation must have |reserved| > 0.
void Unreserve(AllocatorReservationKey, size_t count) __TA_EXCLUDES(lock_);
// Allocate / de-allocate elements from the given reservation. This persists the results of any
// pending allocations/deallocations.
// Since elements are only ever swapped synchronously, all elements represented in the
// allocations_ and deallocations_ bitmaps are guaranteed to belong to only one Vnode. This method
// should only be called in the same thread as the block swaps -- i.e. we should never be
// resolving blocks for more than one vnode at a time.
void Commit(PendingWork* transaction, AllocatorReservation* reservation) __TA_EXCLUDES(lock_);
friend class PendingChange; // For AddPendingChange & RemovePendingChange.
Allocator(std::unique_ptr<AllocatorStorage> storage)
: reserved_(0), first_free_(0), storage_(std::move(storage)) {}
zx::result<> LoadStorage(fs::BufferedOperationsBuilder* builder) __TA_EXCLUDES(lock_);
// See |GetAvailable()|.
size_t GetAvailableLocked() const __TA_REQUIRES(lock_);
// Grows the map to |new_size|, returning the current size.
zx::result<size_t> GrowMapLocked(size_t new_size) __TA_REQUIRES(lock_);
// Acquire direct access to the underlying map storage.
WriteData GetMapDataLocked() __TA_REQUIRES(lock_);
// Find and return a free element. This should only be called when reserved_ > 0, ensuring that at
// least one free element must exist. This currently assumes that first_free_ is accurately set.
size_t FindLocked() const __TA_REQUIRES(lock_);
// Find the next unreserved element starting from |start|. Like FindLocked, this should only be
// called when reserved_ > 0.
size_t FindNextUnreserved(size_t start) const __TA_REQUIRES(lock_);
// Adds & removes |change| from the vector of pending changes.
void AddPendingChange(PendingChange* change);
void RemovePendingChange(PendingChange* change);
// Protects the allocator's metadata.
// Does NOT guard the allocator |storage_|.
mutable std::mutex lock_;
// Total number of elements reserved by AllocatorReservation objects. Represents the maximum
// number of elements that are allowed to be allocated or swapped in at a given time. Once an
// element is marked for allocation or swap, the reserved_ count is updated accordingly. Remaining
// reserved blocks will be committed by the end of each Vnode operation, with the exception of
// copy-on-write data blocks. These will be committed asynchronously via the WorkQueue thread.
// This means that at the time of reservation if |reserved_| > 0, all reserved blocks must
// belong to vnodes which are already enqueued in the WorkQueue thread.
size_t reserved_ __TA_GUARDED(lock_);
// Index of the first free element in the map.
size_t first_free_ __TA_GUARDED(lock_);
// Represents the Allocator's backing storage.
std::unique_ptr<AllocatorStorage> storage_;
// A bitmap interface into |storage_|.
RawBitmap map_ __TA_GUARDED(lock_);
std::vector<PendingChange*> pending_changes_ __TA_GUARDED(lock_);
} // namespace minfs